<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            LeetCode栈&amp;队列 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">LeetCode栈&amp;队列</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2019-10-01 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>17.5k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>83 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="20-有效的括号"><a href="#20-有效的括号" class="headerlink" title="20. 有效的括号"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/valid-parentheses/" >20. 有效的括号<i class="fas fa-external-link-alt"></i></a></h2><p>Given a string containing just the characters <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, <code>&#39;&#123;&#39;</code>, <code>&#39;&#125;&#39;</code>, <code>&#39;[&#39;</code> and <code>&#39;]&#39;</code>, determine if the input string is valid.</p>
<p>An input string is valid if:</p>
<ol>
<li>Open brackets must be closed by the same type of brackets.</li>
<li>Open brackets must be closed in the correct order.</li>
</ol>
<p>Note that an empty string is also considered valid.</p>
<p><strong>Example 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: <span class="string">&quot;()&quot;</span></span><br><span class="line">Output: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>Example 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: <span class="string">&quot;()[]&#123;&#125;&quot;</span></span><br><span class="line">Output: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>Example 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: <span class="string">&quot;(]&quot;</span></span><br><span class="line">Output: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>Example 4:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: <span class="string">&quot;([)]&quot;</span></span><br><span class="line">Output: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>Example 5:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: <span class="string">&quot;&#123;[]&#125;&quot;</span></span><br><span class="line">Output: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这道题只要学过数据结构的肯定会做，典型的利用栈的题</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isValid2</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s.length()&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Stack&lt;Character&gt; stack=<span class="keyword">new</span> Stack();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;(&#x27;</span> || s.charAt(i)==<span class="string">&#x27;&#123;&#x27;</span> || s.charAt(i)==<span class="string">&#x27;[&#x27;</span>)&#123;</span><br><span class="line">            stack.push(s.charAt(i));</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//注意这种情况，一开始就是])&#125;</span></span><br><span class="line">            <span class="keyword">if</span>(stack.isEmpty())&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">char</span> p=s.charAt(i);</span><br><span class="line">            <span class="keyword">if</span>( (p==<span class="string">&#x27;)&#x27;</span> &amp;&amp; stack.pop()!=<span class="string">&#x27;(&#x27;</span>) || (p==<span class="string">&#x27;]&#x27;</span> &amp;&amp; stack.pop()!=<span class="string">&#x27;[&#x27;</span>) || (p==<span class="string">&#x27;&#125;&#x27;</span> &amp;&amp; stack.pop()!=<span class="string">&#x27;&#123;&#x27;</span>))&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>其实和上面的解法是一样的，只不过是用的stack是自己用数组简单封装的栈</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MyStack</span>&lt;<span class="title">T</span>&gt;</span>&#123;</span><br><span class="line"></span><br><span class="line">    T [] objValues=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> top=-<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyStack</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        objValues= (T[]) <span class="keyword">new</span> Object[size];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(T obj)</span></span>&#123;</span><br><span class="line">        objValues[++top]=obj;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> T <span class="title">peek</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (top&lt;<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">&quot;stack is isEmpty&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> objValues[top];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> T <span class="title">pop</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (top&lt;<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">&quot;stack is isEmpty&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//覆盖</span></span><br><span class="line">        <span class="keyword">return</span> objValues[top--];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> top&lt;<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>3ms，94%，比之前快了一点，去看了下Stack的源码，它的pop是真的删除，我的只是移动了指针，所以效率会高很多</p>
<blockquote>
<p>后面的题可能还会利用这个<code>MyStack</code></p>
</blockquote>
<p><strong>解法三</strong></p>
<p>今天看面筋看到一个写这道题，要求O(1)的空间复杂度</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isValid</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s.length()&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(<span class="keyword">true</span>)&#123;</span><br><span class="line">        <span class="keyword">int</span> len=s.length();</span><br><span class="line">        s=s.replace(<span class="string">&quot;&#123;&#125;&quot;</span>,<span class="string">&quot;&quot;</span>);</span><br><span class="line">        s=s.replace(<span class="string">&quot;()&quot;</span>,<span class="string">&quot;&quot;</span>);</span><br><span class="line">        s=s.replace(<span class="string">&quot;[]&quot;</span>,<span class="string">&quot;&quot;</span>);</span><br><span class="line">        <span class="keyword">if</span> (len==s.length()) &#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="string">&quot;&quot;</span>.equals(s);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>100ms，效率感人，感觉应该说的是这种做法吧，当然还可以写正则表达式来匹配，但是我不太会写。。。</p>
<h2 id="678-有效的括号字符串"><a href="#678-有效的括号字符串" class="headerlink" title="678. 有效的括号字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/valid-parenthesis-string/" >678. 有效的括号字符串<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：</p>
<ol>
<li>任何左括号 <code>(</code> 必须有相应的右括号 <code>)</code>。</li>
<li>任何右括号 <code>)</code> 必须有相应的左括号 <code>(</code> 。</li>
<li>左括号 <code>(</code> 必须在对应的右括号之前 <code>)</code>。</li>
<li><code>*</code> 可以被视为单个右括号 <code>)</code> ，或单个左括号 <code>(</code> ，或一个空字符串。</li>
<li>一个空字符串也被视为有效字符串。</li>
</ol>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;()&quot;</span></span><br><span class="line">输出: True</span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;(*)&quot;</span></span><br><span class="line">输出: True</span><br></pre></td></tr></table></figure>


<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;(*))&quot;</span></span><br><span class="line">输出: True</span><br></pre></td></tr></table></figure>


<p><strong>注意:</strong></p>
<ol>
<li>字符串大小将在 [1，100] 范围内。</li>
</ol>
<p><strong>解法一</strong></p>
<p>看面筋看到的这一题，还是挺有意思的，评论区有人说了双栈，然后今天来试了下</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">checkValidString</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    Stack&lt;Integer&gt; bracketStack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    Stack&lt;Integer&gt; starStack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i)==<span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">            bracketStack.push(i);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;*&#x27;</span>)&#123;</span><br><span class="line">            starStack.push(i);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (bracketStack.isEmpty()) &#123;</span><br><span class="line">                <span class="keyword">if</span> (starStack.isEmpty()) &#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                starStack.pop();</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                bracketStack.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//消除左括号</span></span><br><span class="line">    <span class="keyword">while</span>(!starStack.isEmpty() &amp;&amp; !bracketStack.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">if</span>(starStack.peek()&gt;bracketStack.peek())&#123; <span class="comment">//这里的逻辑不太好，其实可以很简单</span></span><br><span class="line">            bracketStack.pop();</span><br><span class="line">        &#125;</span><br><span class="line">        starStack.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> bracketStack.isEmpty();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>很可惜没有<code>bugfree</code>，最后对左括号的判断改了好几次，一开始写的<code>bracketStack.size()&lt;=starStack().size()</code>  然后提交后才意识到还要 <code>&quot;*(&quot;</code> 这样的情况，然后要消除这种情况也简单，一开始我再栈中存的就是index，从star栈里面取比bracket栈index大的，然后消除，最后再看括号栈是不是空</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//2020.4.10重写一下</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">checkValidString</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    Deque&lt;Integer&gt; helpStack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;(&#x27;</span>)&#123;</span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;)&#x27;</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(!stack.isEmpty())&#123;</span><br><span class="line">                stack.pop();</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">if</span>(helpStack.isEmpty())&#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                helpStack.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            helpStack.push(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; !helpStack.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">if</span>(stack.pop()&gt;helpStack.pop())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="921-使括号有效的最少添加"><a href="#921-使括号有效的最少添加" class="headerlink" title="921. 使括号有效的最少添加"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/" >921. 使括号有效的最少添加<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个由 <code>&#39;(&#39;</code> 和 <code>&#39;)&#39;</code> 括号组成的字符串 <code>S</code>，我们需要添加最少的括号（ <code>&#39;(&#39;</code> 或是 <code>&#39;)&#39;</code>，可以在任何位置），以使得到的括号字符串有效。</p>
<p>从形式上讲，只有满足下面几点之一，括号字符串才是有效的：</p>
<ul>
<li>它是一个空字符串，或者</li>
<li>它可以被写成 <code>AB</code> （<code>A</code> 与 <code>B</code> 连接）, 其中 <code>A</code> 和 <code>B</code> 都是有效字符串，或者</li>
<li>它可以被写作 <code>(A)</code>，其中 <code>A</code> 是有效字符串。</li>
</ul>
<p>给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;())&quot;</span></span><br><span class="line">输出：<span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;(((&quot;</span></span><br><span class="line">输出：<span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;()&quot;</span></span><br><span class="line">输出：<span class="number">0</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;()))((&quot;</span></span><br><span class="line">输出：<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>S.length &lt;= 1000</code></li>
<li><code>S</code> 只包含 <code>&#39;(&#39;</code> 和 <code>&#39;)&#39;</code> 字符。</li>
</ol>
<p><strong>解法一</strong></p>
<p>没啥好说的，easy题</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minAddToMakeValid</span><span class="params">(String S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> wa=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;S.length();i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(S.charAt(i)==<span class="string">&#x27;(&#x27;</span>)&#123;</span><br><span class="line">            left++;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span>(left&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                left--;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                wa++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> wa+left;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="394-字符串解码"><a href="#394-字符串解码" class="headerlink" title="394. 字符串解码"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/decode-string/" >394. 字符串解码<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个经过编码的字符串，返回它解码后的字符串。</p>
<p>编码规则为: <code>k[encoded_string]</code>，表示其中方括号内部的 <code>encoded_string</code> 正好重复 k 次。注意 k 保证为正整数。</p>
<p>你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。</p>
<p>此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">s = <span class="string">&quot;3[a]2[bc]&quot;</span>, 返回 <span class="string">&quot;aaabcbc&quot;</span>.</span><br><span class="line">s = <span class="string">&quot;3[a2[c]]&quot;</span>, 返回 <span class="string">&quot;accaccacc&quot;</span>.</span><br><span class="line">s = <span class="string">&quot;2[abc]3[cd]ef&quot;</span>, 返回 <span class="string">&quot;abcabccdcdcdef&quot;</span>.</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>借助栈直接在原字符上做改动</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">decodeString</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s==<span class="keyword">null</span> || s.length()&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;&quot;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//转换为StringBuilder比较好处理,且效率较高</span></span><br><span class="line">    StringBuilder sb=<span class="keyword">new</span> StringBuilder(s);</span><br><span class="line">    Stack&lt;Integer&gt;  stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>;<span class="comment">//遍历索引</span></span><br><span class="line">    <span class="keyword">while</span>(i&lt;sb.length()) &#123;</span><br><span class="line">        <span class="keyword">if</span> (sb.charAt(i)==<span class="string">&#x27;[&#x27;</span>) &#123;</span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(sb.charAt(i)==<span class="string">&#x27;]&#x27;</span>)&#123;</span><br><span class="line">            <span class="keyword">int</span> left=stack.pop();<span class="comment">//对应左括号索引</span></span><br><span class="line">            String temp=sb.substring(left+<span class="number">1</span>,i);<span class="comment">//相邻括号中的字符</span></span><br><span class="line">            <span class="keyword">int</span> preInt=left;</span><br><span class="line">            <span class="comment">//&#x27;[&#x27;前的数字,一开始以为只是个位数,还是挺麻烦的</span></span><br><span class="line">            <span class="keyword">while</span>(preInt-<span class="number">1</span>&gt;=<span class="number">0</span> &amp;&amp; sb.charAt(preInt-<span class="number">1</span>)&gt;=<span class="string">&#x27;0&#x27;</span> &amp;&amp; sb.charAt(preInt-<span class="number">1</span>) &lt;=<span class="string">&#x27;9&#x27;</span>)&#123;</span><br><span class="line">                preInt--;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//repeat次数</span></span><br><span class="line">            <span class="keyword">int</span> repeat=Integer.valueOf(sb.substring(preInt,left));</span><br><span class="line">            <span class="comment">//删除 k[encoded_string] </span></span><br><span class="line">            sb.delete(preInt,Math.min(i+<span class="number">1</span>,sb.length()));</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;repeat;j++) &#123;</span><br><span class="line">                <span class="comment">//从k位置重新插入字符</span></span><br><span class="line">                sb.insert(preInt,temp);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//重新定位索引到尾部</span></span><br><span class="line">            i=preInt+(repeat*temp.length())-<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        i++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sb.toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>一开始是想用一个额外的String来保存结果，结果发现比较麻烦，索性直接将原字符转换为StringBuilder，然后借助api直接在原字符上做改动，因为是在原字符上做改动，所以索引的变化需要额外的注意，这也是最麻烦的一点，需要停下来稍微思考下才能确定，其他的还好，正常的思路，最初WA了一发是因为忽略了前面的数字可能是多位数😂</p>
<p><strong>解法二</strong></p>
<p>递归的方式，改成<code>StringBuilder</code>应该会好一点😂</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> index=<span class="number">0</span>; <span class="comment">//字符索引下标</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">decodeString</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s==<span class="keyword">null</span> || s.length()&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;&quot;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    String sb=<span class="string">&quot;&quot;</span>;</span><br><span class="line">    <span class="keyword">while</span>(index&lt;s.length())&#123;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(index)==<span class="string">&#x27;]&#x27;</span>) &#123; <span class="comment">//遇到右括号就结束</span></span><br><span class="line">            index++;<span class="comment">//index定位到右括号下一个</span></span><br><span class="line">            <span class="keyword">return</span> sb;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(s.charAt(index)&gt;=<span class="string">&#x27;0&#x27;</span> &amp;&amp; s.charAt(index)&lt;=<span class="string">&#x27;9&#x27;</span>)&#123;</span><br><span class="line">            <span class="keyword">int</span> temp=index;</span><br><span class="line">            <span class="keyword">while</span>(index&lt;s.length() &amp;&amp; s.charAt(index)!=<span class="string">&#x27;[&#x27;</span>)&#123;</span><br><span class="line">                index++;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">int</span> repeat=Integer.valueOf(s.substring(temp,index));</span><br><span class="line">            index++;<span class="comment">//跳过&#x27;[&#x27;</span></span><br><span class="line">            String rs=decodeString(s);<span class="comment">//从左括号开始</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;repeat;i++) &#123;</span><br><span class="line">                sb+=rs;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            sb+=s.charAt(index++);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sb;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h2 id="344-反转字符串"><a href="#344-反转字符串" class="headerlink" title="344. 反转字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-string/" >344. 反转字符串<i class="fas fa-external-link-alt"></i></a></h2><p>编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。</p>
<p>不要给另外的数组分配额外的空间，你必须<strong>原地修改输入数组</strong>、使用 O(1) 的额外空间解决这一问题。</p>
<p>你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。</p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;h&quot;</span>,<span class="string">&quot;e&quot;</span>,<span class="string">&quot;l&quot;</span>,<span class="string">&quot;l&quot;</span>,<span class="string">&quot;o&quot;</span>]</span><br><span class="line">输出：[<span class="string">&quot;o&quot;</span>,<span class="string">&quot;l&quot;</span>,<span class="string">&quot;l&quot;</span>,<span class="string">&quot;e&quot;</span>,<span class="string">&quot;h&quot;</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;H&quot;</span>,<span class="string">&quot;a&quot;</span>,<span class="string">&quot;n&quot;</span>,<span class="string">&quot;n&quot;</span>,<span class="string">&quot;a&quot;</span>,<span class="string">&quot;h&quot;</span>]</span><br><span class="line">输出：[<span class="string">&quot;h&quot;</span>,<span class="string">&quot;a&quot;</span>,<span class="string">&quot;n&quot;</span>,<span class="string">&quot;n&quot;</span>,<span class="string">&quot;a&quot;</span>,<span class="string">&quot;H&quot;</span>]</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>很久之前做的了，本来是想单独搞一个递归专题，感觉没啥必要就直接加到一起了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">reverseString</span><span class="params">(<span class="keyword">char</span>[] s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s==<span class="keyword">null</span>||s.length&lt;=<span class="number">1</span>)<span class="keyword">return</span>;</span><br><span class="line">    reverseString(s,<span class="number">0</span>,s.length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">reverseString</span><span class="params">(<span class="keyword">char</span>[] s,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l&gt;=r)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">char</span> temp=s[l];</span><br><span class="line">    s[l]=s[r];</span><br><span class="line">    s[r]=temp;</span><br><span class="line">    reverseString(s,++l,--r);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="150-逆波兰表达式求值"><a href="#150-逆波兰表达式求值" class="headerlink" title="150. 逆波兰表达式求值"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/" >150. 逆波兰表达式求值<i class="fas fa-external-link-alt"></i></a></h2><p>根据<a class="link"   target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437" >逆波兰表示法<i class="fas fa-external-link-alt"></i></a>，求表达式的值。</p>
<p>有效的运算符包括 <code>+, -, *, /</code> 。每个运算对象可以是整数，也可以是另一个逆波兰表达式</p>
<p>说明：</p>
<ul>
<li>整数除法只保留整数部分。</li>
<li>给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。</li>
</ul>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="string">&quot;2&quot;</span>, <span class="string">&quot;1&quot;</span>, <span class="string">&quot;+&quot;</span>, <span class="string">&quot;3&quot;</span>, <span class="string">&quot;*&quot;</span>]</span><br><span class="line">输出: <span class="number">9</span></span><br><span class="line">解释: ((<span class="number">2</span> + <span class="number">1</span>) * <span class="number">3</span>) = <span class="number">9</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="string">&quot;4&quot;</span>, <span class="string">&quot;13&quot;</span>, <span class="string">&quot;5&quot;</span>, <span class="string">&quot;/&quot;</span>, <span class="string">&quot;+&quot;</span>]</span><br><span class="line">输出: <span class="number">6</span></span><br><span class="line">解释: (<span class="number">4</span> + (<span class="number">13</span> / <span class="number">5</span>)) = <span class="number">6</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="string">&quot;10&quot;</span>, <span class="string">&quot;6&quot;</span>, <span class="string">&quot;9&quot;</span>, <span class="string">&quot;3&quot;</span>, <span class="string">&quot;+&quot;</span>, <span class="string">&quot;-11&quot;</span>, <span class="string">&quot;*&quot;</span>, <span class="string">&quot;/&quot;</span>, <span class="string">&quot;*&quot;</span>, <span class="string">&quot;17&quot;</span>, <span class="string">&quot;+&quot;</span>, <span class="string">&quot;5&quot;</span>, <span class="string">&quot;+&quot;</span>]</span><br><span class="line">输出: <span class="number">22</span></span><br><span class="line">解释: </span><br><span class="line">  ((<span class="number">10</span> * (<span class="number">6</span> / ((<span class="number">9</span> + <span class="number">3</span>) * -<span class="number">11</span>))) + <span class="number">17</span>) + <span class="number">5</span></span><br><span class="line">= ((<span class="number">10</span> * (<span class="number">6</span> / (<span class="number">12</span> * -<span class="number">11</span>))) + <span class="number">17</span>) + <span class="number">5</span></span><br><span class="line">= ((<span class="number">10</span> * (<span class="number">6</span> / -<span class="number">132</span>)) + <span class="number">17</span>) + <span class="number">5</span></span><br><span class="line">= ((<span class="number">10</span> * <span class="number">0</span>) + <span class="number">17</span>) + <span class="number">5</span></span><br><span class="line">= (<span class="number">0</span> + <span class="number">17</span>) + <span class="number">5</span></span><br><span class="line">= <span class="number">17</span> + <span class="number">5</span></span><br><span class="line">= <span class="number">22</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">evalRPN</span><span class="params">(String[] tokens)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//上面自己封装的Stack</span></span><br><span class="line">    MyStack&lt;Integer&gt; stack=<span class="keyword">new</span> MyStack&lt;&gt;(tokens.length);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;tokens.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="string">&quot;+&quot;</span>.equals(tokens[i]))&#123;</span><br><span class="line">            stack.push(stack.pop()+stack.pop());</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span>(<span class="string">&quot;-&quot;</span>.equals(tokens[i]))&#123;</span><br><span class="line">            <span class="keyword">int</span> rd1=stack.pop();</span><br><span class="line">            <span class="keyword">int</span> rd2=stack.pop();</span><br><span class="line">            stack.push(rd2-rd1);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(<span class="string">&quot;*&quot;</span>.equals(tokens[i]))&#123;</span><br><span class="line">            stack.push(stack.pop()*stack.pop());</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(<span class="string">&quot;/&quot;</span>.equals(tokens[i]))&#123;</span><br><span class="line">            <span class="keyword">int</span> div1=stack.pop();</span><br><span class="line">            <span class="keyword">int</span> div2=stack.pop();</span><br><span class="line">            stack.push(div2/div1);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            stack.push(Integer.valueOf(tokens[i]));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> stack.peek();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>12ms，90%，其实一开始看到这个题我是拒绝的，我以为又是啥数学题，然后仔细看了下发现挺简单的，思路就是利用栈，每次遇到符号就pop两个出来进行运算，然后再入栈，值得注意的地方就是减法和除法的顺序</p>
<h2 id="71-简化路径"><a href="#71-简化路径" class="headerlink" title="71. 简化路径"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/simplify-path/" >71. 简化路径<i class="fas fa-external-link-alt"></i></a></h2><p>以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。</p>
<p>在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：<a class="link"   target="_blank" rel="noopener" href="https://blog.csdn.net/u011327334/article/details/50355600" >Linux / Unix中的绝对路径 vs 相对路径<i class="fas fa-external-link-alt"></i></a></p>
<p>请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 <code>/</code>。最后一个目录名（如果存在）<strong>不能</strong>以 / 结尾。此外，规范路径必须是表示绝对路径的<strong>最短</strong>字符串</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;/home/&quot;</span></span><br><span class="line">输出：<span class="string">&quot;/home&quot;</span></span><br><span class="line">解释：注意，最后一个目录名后面没有斜杠。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;/../&quot;</span></span><br><span class="line">输出：<span class="string">&quot;/&quot;</span></span><br><span class="line">解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。</span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;/home//foo/&quot;</span></span><br><span class="line">输出：<span class="string">&quot;/home/foo&quot;</span></span><br><span class="line">解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。</span><br></pre></td></tr></table></figure>


<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;/a/./b/../../c/&quot;</span></span><br><span class="line">输出：<span class="string">&quot;/c&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 5：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;/a/../../b/../c//.//&quot;</span></span><br><span class="line">输出：<span class="string">&quot;/c&quot;</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 6：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：<span class="string">&quot;/a//b////c/d//././/..&quot;</span></span><br><span class="line">输出：<span class="string">&quot;/a/b/c&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> String <span class="title">simplifyPath</span><span class="params">(String path)</span> </span>&#123;</span><br><span class="line">    MyStack&lt;String&gt; stack=<span class="keyword">new</span> MyStack&lt;&gt;(path.length());</span><br><span class="line">    StringBuilder str=<span class="keyword">new</span> StringBuilder(path);</span><br><span class="line">    <span class="comment">//这里划分出来有一部分是空的 &quot;&quot;</span></span><br><span class="line">    String[] s=path.split(<span class="string">&quot;/&quot;</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!stack.isEmpty() &amp;&amp; s[i].equals(<span class="string">&quot;..&quot;</span>)) &#123;</span><br><span class="line">            <span class="comment">//.. 回溯</span></span><br><span class="line">            stack.pop();</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (!<span class="string">&quot;.&quot;</span>.equals(s[i]) &amp;&amp; !<span class="string">&quot;&quot;</span>.equals(s[i]) &amp;&amp; !s[i].equals(<span class="string">&quot;..&quot;</span>) ) &#123;</span><br><span class="line">            <span class="comment">//普通的英文字符abcd</span></span><br><span class="line">            stack.push(s[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (stack.isEmpty()) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;/&quot;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    StringBuilder res=<span class="keyword">new</span> StringBuilder();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;stack.size(); i++) &#123;</span><br><span class="line">        res.append(<span class="string">&quot;/&quot;</span>+stack.get(i));   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toString();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//自己封装的stack</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MyStack</span>&lt;<span class="title">T</span>&gt;</span>&#123;</span><br><span class="line"></span><br><span class="line">    T [] objValues=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> top=-<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyStack</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        objValues= (T[]) <span class="keyword">new</span> Object[size];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(T obj)</span></span>&#123;</span><br><span class="line">        objValues[++top]=obj;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> T <span class="title">peek</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (top&lt;<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">&quot;stack is isEmpty&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> objValues[top];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> T <span class="title">pop</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (top&lt;<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">&quot;stack is isEmpty&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//覆盖</span></span><br><span class="line">        <span class="keyword">return</span> objValues[top--];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> T <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index&gt;top || index &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">&quot;index is wrong&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> objValues[index];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> top&lt;<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> top+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题本来是很简单的，但是我钻到牛角尖去了，一直想着怎么在遍历过程中处理，写了一堆ifelse。。。还是太菜了啊，其实直接按照<code>&quot;/&quot;</code> 划分split字符串然后处理那个数组就可以了</p>
<h2 id="225-用队列实现栈"><a href="#225-用队列实现栈" class="headerlink" title="225. 用队列实现栈"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/implement-stack-using-queues/" >225. 用队列实现栈<i class="fas fa-external-link-alt"></i></a></h2><p>Implement the following operations of a stack using queues.</p>
<ul>
<li>push(x) – Push element x onto stack.</li>
<li>pop() – Removes the element on top of the stack.</li>
<li>top() – Get the top element.</li>
<li>empty() – Return whether the stack is empty.</li>
</ul>
<p><strong>Example:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">MyStack stack = <span class="keyword">new</span> MyStack();</span><br><span class="line"></span><br><span class="line">stack.push(<span class="number">1</span>);</span><br><span class="line">stack.push(<span class="number">2</span>);  </span><br><span class="line">stack.top();   <span class="comment">// returns 2</span></span><br><span class="line">stack.pop();   <span class="comment">// returns 2</span></span><br><span class="line">stack.empty(); <span class="comment">// returns false</span></span><br></pre></td></tr></table></figure>

<p><strong>Notes:</strong></p>
<ul>
<li>You must use <em>only</em> standard operations of a queue – which means only <code>push to back</code>, <code>peek/pop from front</code>, <code>size</code>, and <code>is empty</code> operations are valid.</li>
<li>Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.</li>
<li>You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).</li>
</ul>
<p><strong>解法一</strong></p>
<p>很经典的题</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyStack</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> ArrayDeque&lt;Integer&gt; queue=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Initialize your data structure here. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        queue=<span class="keyword">new</span> ArrayDeque();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Push element x onto stack. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">        queue.add(x);</span><br><span class="line">        <span class="keyword">int</span> size=queue.size();</span><br><span class="line">        <span class="comment">//除了新加入的元素，其他的元素都出队再入队，将新加入的元素推置队列头</span></span><br><span class="line">        <span class="keyword">while</span>(size-- &gt;<span class="number">1</span>)&#123;</span><br><span class="line">            queue.add(queue.pop());</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Removes the element on top of the stack and returns that element. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">       <span class="keyword">return</span>  queue.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/** Get the top element. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> queue.peek();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Returns whether the stack is empty. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">empty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> queue.isEmpty();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>很巧妙的做法，将元素前n-1个出队后再重新入队，<code>1 2 --&gt; 2 1</code> 直接将堆顶推置队列头 ，将每次新加入的元素都放置队列头而不是队尾，这样实际上就完成了逆序的操作</p>
<p>这样push压栈时间复杂度<code>O(N)</code> ，<code>pop/peek</code> 时间复杂度<code>O(1)</code></p>
<p><strong>解法二</strong></p>
<p>适用于push频繁的stack</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MyStack</span></span>&#123;</span><br><span class="line">   <span class="comment">//形式上q1是负责进栈 q2负责出栈</span></span><br><span class="line">    <span class="keyword">private</span> LinkedList inQueue=<span class="keyword">new</span> LinkedList(); </span><br><span class="line">    <span class="keyword">private</span> LinkedList outQueue=<span class="keyword">new</span> LinkedList();</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span>  <span class="keyword">void</span>  <span class="title">add</span><span class="params">(Object obj)</span></span>&#123;</span><br><span class="line">        inQueue.add(obj);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Object <span class="title">pop</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="comment">// q1 ----&gt; q2 留一个</span></span><br><span class="line">        <span class="keyword">while</span>(inQueue.size()&gt;<span class="number">1</span>)&#123;</span><br><span class="line">            outQueue.add(inQueue.poll());</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//交换q1,q2的引用</span></span><br><span class="line">        LinkedList temp;</span><br><span class="line">        temp=inQueue;</span><br><span class="line">        inQueue=outQueue;</span><br><span class="line">        outQueue=temp;</span><br><span class="line">        <span class="keyword">return</span> outQueue.poll();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Object <span class="title">peek</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="comment">//q1 ---&gt;q2 留一个,最后一个不poll,最后poll</span></span><br><span class="line">        <span class="keyword">while</span>(inQueue.size()&gt;<span class="number">1</span>)&#123;</span><br><span class="line">            outQueue.add(inQueue.poll());</span><br><span class="line">            <span class="keyword">if</span>(inQueue.size()==<span class="number">1</span>)&#123;</span><br><span class="line">                outQueue.add(inQueue.peek());</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//交换q1,q2的引用</span></span><br><span class="line">        LinkedList temp;</span><br><span class="line">        temp=inQueue;</span><br><span class="line">        inQueue=outQueue;</span><br><span class="line">        outQueue=temp;</span><br><span class="line">        <span class="keyword">return</span> outQueue.poll();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>两个队列，push压栈时间复杂度<code>O(1)</code>，pop/push出栈时间复杂度<code>O(N)</code> ，出栈的时候将一个队列的前n-1个元素全部加入到另一个队列中作为缓存，然后将最后一个元素出栈，最后别忘了交换两个队列的引用，不然push的时候就会出问题，要保证<code>inQueue</code> 一直是入栈的队列，其中存放着所有的元素</p>
<h2 id="232-用栈实现队列"><a href="#232-用栈实现队列" class="headerlink" title="232. 用栈实现队列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/implement-queue-using-stacks/" >232. 用栈实现队列<i class="fas fa-external-link-alt"></i></a></h2><p>Implement the following operations of a queue using stacks.</p>
<ul>
<li>push(x) – Push element x to the back of queue.</li>
<li>pop() – Removes the element from in front of queue.</li>
<li>peek() – Get the front element.</li>
<li>empty() – Return whether the queue is empty.</li>
</ul>
<p><strong>Example:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">MyQueue queue = <span class="keyword">new</span> MyQueue();</span><br><span class="line"></span><br><span class="line">queue.push(<span class="number">1</span>);</span><br><span class="line">queue.push(<span class="number">2</span>);  </span><br><span class="line">queue.peek();  <span class="comment">// returns 1</span></span><br><span class="line">queue.pop();   <span class="comment">// returns 1</span></span><br><span class="line">queue.empty(); <span class="comment">// returns false</span></span><br></pre></td></tr></table></figure>

<p><strong>Notes:</strong></p>
<ul>
<li>You must use <em>only</em> standard operations of a stack – which means only <code>push to top</code>, <code>peek/pop from top</code>, <code>size</code>, and <code>is empty</code> operations are valid.</li>
<li>Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.</li>
<li>You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).</li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyQueue</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    Stack&lt;Integer&gt; inStack=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    Stack&lt;Integer&gt; outStack=<span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">/** Initialize your data structure here. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Stack2Queue232</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        inStack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        outStack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Push element x to the back of queue. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">        inStack.push(x);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Removes the element from in front of queue and returns that element. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        s2s();</span><br><span class="line">        <span class="keyword">return</span> outStack.pop();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Get the front element. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">peek</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        s2s();</span><br><span class="line">        <span class="keyword">return</span> outStack.peek();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Returns whether the queue is empty. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">empty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> outStack.isEmpty() &amp;&amp; inStack.isEmpty();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">s2s</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (outStack.isEmpty()) &#123;</span><br><span class="line">            <span class="keyword">while</span>(!inStack.isEmpty()) &#123;</span><br><span class="line">                outStack.push(inStack.pop());</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;     </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>很上面一题是姊妹题，需要注意的地方就是<code>s2s</code>的时候要确保stack2栈是空的才能push</p>
<h2 id="155-最小栈"><a href="#155-最小栈" class="headerlink" title="155. 最小栈"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/min-stack/" >155. 最小栈<i class="fas fa-external-link-alt"></i></a></h2><p>设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。</p>
<ul>
<li><p>push(x) – 将元素 x 推入栈中。</p>
</li>
<li><p>pop() – 删除栈顶的元素。</p>
</li>
<li><p>top() – 获取栈顶元素。</p>
</li>
<li><p>getMin() – 检索栈中的最小元素。</p>
</li>
</ul>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">MinStack minStack = <span class="keyword">new</span> MinStack();</span><br><span class="line">minStack.push(-<span class="number">2</span>);</span><br><span class="line">minStack.push(<span class="number">0</span>);</span><br><span class="line">minStack.push(-<span class="number">3</span>);</span><br><span class="line">minStack.getMin();   --&gt; 返回 -<span class="number">3.</span></span><br><span class="line">minStack.pop();</span><br><span class="line">minStack.top();      --&gt; 返回 <span class="number">0.</span></span><br><span class="line">minStack.getMin();   --&gt; 返回 -<span class="number">2.</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>利用辅助栈，同步的push和pop</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MinStack</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** initialize your data structure here. */</span></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; stack=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; helpStack=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MinStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        helpStack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">        stack.push(x);</span><br><span class="line">        <span class="keyword">if</span> (helpStack.isEmpty()) &#123;</span><br><span class="line">            helpStack.push(x);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (helpStack.peek()&gt;x) &#123;</span><br><span class="line">                helpStack.push(x);</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                helpStack.push(helpStack.peek());</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        stack.pop();</span><br><span class="line">        helpStack.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> stack.peek();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getMin</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> helpStack.peek();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>在上面的基础上进行空间的优化</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MinStack</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** initialize your data structure here. */</span></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; stack=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; helpStack=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MinStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        helpStack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">        stack.push(x);</span><br><span class="line">        <span class="keyword">if</span> (helpStack.isEmpty()) &#123;</span><br><span class="line">            helpStack.push(x);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (x&lt;=helpStack.peek()) &#123;</span><br><span class="line">            <span class="comment">//相等的也要入栈,不然不好控制后面出栈</span></span><br><span class="line">            helpStack.push(x);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> top=stack.pop();</span><br><span class="line">        <span class="comment">//和辅助栈栈顶相同就出栈</span></span><br><span class="line">        <span class="keyword">if</span>(top==helpStack.peek())&#123;</span><br><span class="line">            helpStack.pop();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">        if(stack.pop()==helpStack.peek())&#123;</span></span><br><span class="line"><span class="comment">            helpStack.pop();</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> stack.peek();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getMin</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> helpStack.peek();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其实这里有一个地方把我卡了一会儿，就是出栈的时候，我开始为了简洁if的条件写的</p>
<p><code>stack.pop()==helpStack.peek()</code> 然后卡在了一个case上，想了半天才意识到是<code>Integer</code>的问题，这里弹出来的是两个<code>Integer</code>并不会自动拆箱，而且值是不在 -128~127之间的，所以就false了</p>
<p><strong>解法三</strong></p>
<p>帅地上看见的解法，在栈中存一个diff差值，代表当前元素和入栈前的min的差值，空间复杂度为O(1)，但是这种做法限制比较多，比如数据的大小会有限制，同时貌似也无法做<code>peek()</code>操作</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MinStack155_2</span></span>&#123;</span><br><span class="line">    <span class="comment">/** initialize your data structure here. */</span></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; stack=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> min=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MinStack155_2</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (stack.isEmpty()) &#123;</span><br><span class="line">            min=x;</span><br><span class="line">            stack.push(<span class="number">0</span>);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">int</span> diff=x-min;</span><br><span class="line">            min=diff&gt;<span class="number">0</span>?min:x;</span><br><span class="line">            stack.push(diff);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> diff=stack.pop();</span><br><span class="line">        <span class="comment">//小于等于0说明 min就是当前真实的栈顶元素,也就是说 min-minPre=diff</span></span><br><span class="line">        min=diff&lt;=<span class="number">0</span>?min-diff:min;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/*public int top() &#123;</span></span><br><span class="line"><span class="comment">        int diff=stack.peek();</span></span><br><span class="line"><span class="comment">        return diff&lt;=0?min:diff-min;</span></span><br><span class="line"><span class="comment">    &#125;*/</span></span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getMin</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> min;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="779-第K个语法符号"><a href="#779-第K个语法符号" class="headerlink" title="779. 第K个语法符号"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/k-th-symbol-in-grammar/" >779. 第K个语法符号<i class="fas fa-external-link-alt"></i></a></h2><p>On the first row, we write a <code>0</code>. Now in every subsequent row, we look at the previous row and replace each occurrence of <code>0</code> with <code>01</code>, and each occurrence of <code>1</code> with <code>10</code>.</p>
<p>Given row <code>N</code> and index <code>K</code>, return the <code>K</code>-th indexed symbol in row <code>N</code>. (The values of <code>K</code> are 1-indexed.) (1 indexed).</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Examples:</span><br><span class="line">Input: N = <span class="number">1</span>, K = <span class="number">1</span></span><br><span class="line">Output: <span class="number">0</span></span><br><span class="line"></span><br><span class="line">Input: N = <span class="number">2</span>, K = <span class="number">1</span></span><br><span class="line">Output: <span class="number">0</span></span><br><span class="line"></span><br><span class="line">Input: N = <span class="number">2</span>, K = <span class="number">2</span></span><br><span class="line">Output: <span class="number">1</span></span><br><span class="line"></span><br><span class="line">Input: N = <span class="number">4</span>, K = <span class="number">5</span></span><br><span class="line">Output: <span class="number">1</span></span><br><span class="line"></span><br><span class="line">Explanation:</span><br><span class="line">row <span class="number">1</span>: <span class="number">0</span></span><br><span class="line">row <span class="number">2</span>: <span class="number">01</span></span><br><span class="line">row <span class="number">3</span>: <span class="number">0110</span></span><br><span class="line">row <span class="number">4</span>: <span class="number">01101001</span></span><br></pre></td></tr></table></figure>

<p><strong>Note:</strong></p>
<ol>
<li><code>N</code> will be an integer in the range <code>[1, 30]</code>.</li>
<li><code>K</code> will be an integer in the range <code>[1, 2^(N-1)]</code>.</li>
</ol>
<p><strong>解法一</strong></p>
<p>找规律，前半部分和后半部分是有一定规律的，把前六行都写出来</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">第一行: <span class="number">0</span></span><br><span class="line">第二行: <span class="number">01</span></span><br><span class="line">第三行: <span class="number">01</span>|<span class="number">10</span></span><br><span class="line">第四行: <span class="number">01</span> <span class="number">10</span>|<span class="number">10</span> <span class="number">01</span></span><br><span class="line">第五行: <span class="number">01</span> <span class="number">10</span> <span class="number">10</span> <span class="number">01</span>|<span class="number">10</span> <span class="number">01</span> <span class="number">01</span> <span class="number">10</span></span><br><span class="line">第六行: <span class="number">01</span> <span class="number">10</span> <span class="number">10</span> <span class="number">01</span> <span class="number">10</span> <span class="number">01</span> <span class="number">01</span> <span class="number">10</span> | <span class="number">10</span> <span class="number">01</span> <span class="number">01</span> <span class="number">10</span> <span class="number">01</span> <span class="number">10</span> <span class="number">10</span> <span class="number">01</span></span><br></pre></td></tr></table></figure>

<p>  N%2!=0 对称, 第K个等于 2^(N-1)-K+1<br>  N%2==0 互补对称</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">kthGrammar</span><span class="params">(<span class="keyword">int</span> N, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(K==<span class="number">1</span> || N==<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(K==<span class="number">2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> len=<span class="number">1</span>&lt;&lt;(N-<span class="number">1</span>); <span class="comment">//当前行长度</span></span><br><span class="line">    <span class="keyword">if</span>(K&gt;len/<span class="number">2</span>)&#123; <span class="comment">//大于1/2</span></span><br><span class="line">        <span class="comment">//结合上面的规律，找前半部分和自己等价的位置</span></span><br><span class="line">        <span class="keyword">if</span>(N%<span class="number">2</span>!=<span class="number">0</span>)&#123; </span><br><span class="line">            K=len-K+<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span>(K%<span class="number">2</span>==<span class="number">0</span>)&#123;</span><br><span class="line">                K=len-K+<span class="number">2</span>;  </span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                K=len-K;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//去上一行继续</span></span><br><span class="line">    <span class="keyword">return</span> kthGrammar(N-<span class="number">1</span>,K);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>时间复杂第O(N)，思路还算清晰，最开始没想到用<code>位运算</code>来算长度，用的<code>pow()</code>最后效率差不多，可能是底层做了优化。</p>
<p><strong>解法二</strong></p>
<p>这种解法实际上就是把整个序列看作一颗满二叉树，每个节点的值和父节点其实是有对应关系的，如果K是偶数那么就和父节点的值相反，否则就相同，所以我们可以递归的去找父节点对应的index的值。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//01排列</span></span><br><span class="line"><span class="comment">//              0</span></span><br><span class="line"><span class="comment">//          /        \   </span></span><br><span class="line"><span class="comment">//      0                1</span></span><br><span class="line"><span class="comment">//    /   \            /    \</span></span><br><span class="line"><span class="comment">//  0       1        1       0</span></span><br><span class="line"><span class="comment">// / \     /  \     /  \    / \ </span></span><br><span class="line"><span class="comment">//0   1   1    0   1    0  0   1</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">kthGrammar</span><span class="params">(<span class="keyword">int</span> N, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (K==<span class="number">1</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="comment">//(K+1)/2是对应父节点的index</span></span><br><span class="line">    <span class="keyword">int</span> parent=kthGrammar(N-<span class="number">1</span>,(K+<span class="number">1</span>)/<span class="number">2</span>);</span><br><span class="line">    <span class="comment">//取反</span></span><br><span class="line">    <span class="keyword">int</span> f_parent=-(parent-<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">if</span> (K%<span class="number">2</span>==<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> f_parent;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> parent;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>时间复杂度依然是<code>O(N)</code> 但是比上面那种要更清晰明了</p>
<p><strong>解法三</strong></p>
<p>这个解法其实和上面的思路是一样的，都是利用父节点和K的奇偶来判断，其实仔细看上面的代码你会发现N其实并没有实际的意义，具体K的值只和K本身有关，下面的解法就没有用到N.</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">kthGrammar3</span><span class="params">(<span class="keyword">int</span> N, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">boolean</span> r=<span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">while</span>(K&gt;<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span> (K%<span class="number">2</span>==<span class="number">0</span>) &#123;</span><br><span class="line">            K=K/<span class="number">2</span>;</span><br><span class="line">            r=!r;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            K=(K+<span class="number">1</span>)/<span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> r?<span class="number">1</span>:<span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题其实还有一种解法，利用二进制，对K做奇偶检验，貌似时间复杂度是O(1)。</p>
<h2 id="50-Pow-x-n"><a href="#50-Pow-x-n" class="headerlink" title="50. Pow(x, n)"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/powx-n/" >50. Pow(x, n)<i class="fas fa-external-link-alt"></i></a></h2><p>实现 pow(<em>x</em>, <em>n</em>) ，即计算 x 的 n 次幂函数。</p>
<p><strong>解法一</strong></p>
<p>这里就要介绍一种快速幂算法了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">double</span> <span class="title">fastPow</span><span class="params">(<span class="keyword">double</span> x,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(n&lt;<span class="number">0</span>)&#123;</span><br><span class="line">        x=<span class="number">1</span>/x;</span><br><span class="line">        n=-n;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">double</span> res=fastPow(x,n/<span class="number">2</span>);</span><br><span class="line">    <span class="keyword">if</span>(n%<span class="number">2</span>==<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> res*res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res*res*x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>核心思想就是 <code>x^n=(x^2/n)^2</code>，常规累乘的方式计算时间复杂度是O(N)因为要遍历所有的元素，但是其实知道了<code>x^n/2</code>之后 <code>x^n</code>就可以直接平方得到了不用继续遍历，整体时间复杂度为O(logN) </p>
<p>2019.8.20，又写了一遍，提交然后没过。看了下给的测试用例，最后一个给的n是 <code>-2^31</code> 也就是int整数的最小值，int类型的取值范围是 <code>-2^31 ~ 2^31-1</code> 而这个负值在这里取反之后会直接溢出最后得到的还是 <code>-2^31</code> ，所以这里这样写 if会执行两次，x就又会变回来，所以结果直接就是<code>Infinity</code>无穷大了，所以为了保证if只会执行一次可以将其封装一下</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">double</span> <span class="title">myPow</span><span class="params">(<span class="keyword">double</span> x, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n&lt;<span class="number">0</span>)&#123;</span><br><span class="line">        x=<span class="number">1</span>/x;</span><br><span class="line">        n=-n;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> fastPow(x,n);</span><br><span class="line">&#125; </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">double</span> <span class="title">fastPow</span><span class="params">(<span class="keyword">double</span> x,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1.0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">double</span>  half=fastPow(x,n/<span class="number">2</span>);</span><br><span class="line">    <span class="keyword">if</span>(n%<span class="number">2</span>==<span class="number">0</span>)</span><br><span class="line">        <span class="keyword">return</span> half*half;</span><br><span class="line">    <span class="keyword">return</span> half*half*x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="5222-分割平衡字符串"><a href="#5222-分割平衡字符串" class="headerlink" title="5222. 分割平衡字符串"></a>5222. 分割平衡字符串</h2><p>在一个「平衡字符串」中，’L’ 和 ‘R’ 字符的数量是相同的。</p>
<p>给出一个平衡字符串 <code>s</code>，请你将它分割成尽可能多的平衡字符串。</p>
<p>返回可以通过分割得到的平衡字符串的最大数量</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;RLRRLLRLRL&quot;</span></span><br><span class="line">输出：<span class="number">4</span></span><br><span class="line">解释：s 可以分割为 <span class="string">&quot;RL&quot;</span>, <span class="string">&quot;RRLL&quot;</span>, <span class="string">&quot;RL&quot;</span>, <span class="string">&quot;RL&quot;</span>, 每个子字符串中都包含相同数量的 <span class="string">&#x27;L&#x27;</span> 和 <span class="string">&#x27;R&#x27;</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;RLLLLRRRLR&quot;</span></span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释：s 可以分割为 <span class="string">&quot;RL&quot;</span>, <span class="string">&quot;LLLRRR&quot;</span>, <span class="string">&quot;LR&quot;</span>, 每个子字符串中都包含相同数量的 <span class="string">&#x27;L&#x27;</span> 和 <span class="string">&#x27;R&#x27;</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;LLLLRRRR&quot;</span></span><br><span class="line">输出：<span class="number">1</span></span><br><span class="line">解释：s 只能保持原样 <span class="string">&quot;LLLLRRRR&quot;</span>.</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= s.length &lt;= 1000</code></li>
<li><code>s[i] = &#39;L&#39; 或 &#39;R&#39;</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>19.10.13的周赛的第1题，果然比赛和刷题还是不一样，差点没做出来。。。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">balancedStringSplit</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s.length()%<span class="number">2</span>==<span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Stack&lt;Character&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++)&#123;</span><br><span class="line">        <span class="keyword">if</span> (!stack.isEmpty() )&#123;</span><br><span class="line">            <span class="keyword">if</span>(s.charAt(i)==stack.peek()) &#123;</span><br><span class="line">                stack.push(s.charAt(i));    </span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                stack.pop();</span><br><span class="line">                <span class="keyword">if</span> (stack.isEmpty()) &#123;</span><br><span class="line">                    count++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            stack.push(s.charAt(i));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1249-移除无效的括号"><a href="#1249-移除无效的括号" class="headerlink" title="1249. 移除无效的括号"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses/" >1249. 移除无效的括号<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个由 ‘(‘、’)’ 和小写字母组成的字符串 s。</p>
<p>你需要从字符串中删除最少数目的 ‘(‘ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。</p>
<p>请返回任意一个合法字符串。</p>
<p>有效「括号字符串」应当符合以下 <strong>任意一条</strong> 要求：</p>
<ul>
<li>空字符串或只包含小写字母的字符串</li>
<li>可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」</li>
<li>可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」</li>
</ul>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;lee(t(c)o)de)&quot;</span></span><br><span class="line">输出：<span class="string">&quot;lee(t(c)o)de&quot;</span></span><br><span class="line">解释：<span class="string">&quot;lee(t(co)de)&quot;</span> , <span class="string">&quot;lee(t(c)ode)&quot;</span> 也是一个可行答案。</span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;a)b(c)d&quot;</span></span><br><span class="line">输出：<span class="string">&quot;ab(c)d&quot;</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;))((&quot;</span></span><br><span class="line">输出：<span class="string">&quot;&quot;</span></span><br><span class="line">解释：空字符串也是有效的</span><br></pre></td></tr></table></figure>


<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;(a(b(c)d)&quot;</span></span><br><span class="line">输出：<span class="string">&quot;a(b(c)d)&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= s.length &lt;= 10^5</code></li>
<li><code>s[i]</code> 可能是 <code>&#39;(&#39;</code>、<code>&#39;)&#39;</code> 或英文小写字母 </li>
</ul>
<p><strong>解法一</strong></p>
<p>11.3周赛第三题，这题倒是没什么障碍，用栈就ok，不过我这里实现的不太好，replace时间复杂度略高，应该用一个数组做mark最后用StringBuilder做append应该效率会高很多</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">minRemoveToMakeValid</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    StringBuilder sb=<span class="keyword">new</span> StringBuilder(s);</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i)&gt;=<span class="string">&#x27;a&#x27;</span> &amp;&amp; s.charAt(i)&lt;=<span class="string">&#x27;z&#x27;</span>) &#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i)==<span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (stack.isEmpty()) &#123;</span><br><span class="line">                sb.replace(i,i+<span class="number">1</span>,<span class="string">&quot;*&quot;</span>);    </span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                stack.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i)==<span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (!stack.isEmpty()) &#123;</span><br><span class="line">        <span class="keyword">int</span> temp=stack.pop();</span><br><span class="line">        sb.replace(temp,temp+<span class="number">1</span>,<span class="string">&quot;*&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    String res=sb.toString().replace(<span class="string">&quot;*&quot;</span>,<span class="string">&quot;&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="856-括号的分数"><a href="#856-括号的分数" class="headerlink" title="856. 括号的分数"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/score-of-parentheses/" >856. 括号的分数<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：</p>
<ul>
<li>() 得 1 分。</li>
<li>AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。</li>
<li>(A) 得 2 * A 分，其中 A 是平衡括号字符串。</li>
</ul>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入： <span class="string">&quot;()&quot;</span></span><br><span class="line">输出： <span class="number">1</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入： <span class="string">&quot;(())&quot;</span></span><br><span class="line">输出： <span class="number">2</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入： <span class="string">&quot;()()&quot;</span></span><br><span class="line">输出： <span class="number">2</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入： <span class="string">&quot;(()(()))&quot;</span></span><br><span class="line">输出： <span class="number">6</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li>S 是平衡括号字符串，且只含有 ( 和 ) 。</li>
<li>2 &lt;= S.length &lt;= 50</li>
</ol>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">scoreOfParentheses</span><span class="params">(String S)</span> </span>&#123;</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;S.length();i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(S.charAt(i)==<span class="string">&#x27;(&#x27;</span>)&#123;</span><br><span class="line">            stack.push(-<span class="number">11111</span>);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//遇到右括号,下面的分支都是处理 &quot;)&quot;</span></span><br><span class="line">            <span class="keyword">int</span> top=stack.peek();</span><br><span class="line">            <span class="keyword">if</span>(top == -<span class="number">11111</span>)&#123; <span class="comment">//栈顶是左括号，将 ( --&gt; 1</span></span><br><span class="line">                stack.pop();</span><br><span class="line">                stack.push(<span class="number">1</span>);</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">int</span> sum=<span class="number">0</span>; <span class="comment">//遇到数值了</span></span><br><span class="line">                <span class="keyword">while</span>(!stack.isEmpty())&#123;</span><br><span class="line">                    <span class="keyword">int</span> temp=stack.pop();</span><br><span class="line">                    <span class="comment">//弹出去,直到遇到 &quot;(&quot;就*2,其实就是把&quot;(1&quot;--&gt;2</span></span><br><span class="line">                    <span class="keyword">if</span>(temp==-<span class="number">11111</span>)&#123; </span><br><span class="line">                        sum*=<span class="number">2</span>;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    sum+=temp;</span><br><span class="line">                &#125;</span><br><span class="line">                stack.push(sum);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(!stack.isEmpty()) res+=stack.pop();</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这种解法一开始也没想出来，其实这种就类似于消消乐游戏一样，就按照题目的逻辑来写，从左向右，栈中存标识左括号的数值，这里我用的<code>-11111</code> 表示<code>（</code> ，然后向右移动，一边移动一边将<code>（）</code>给消除掉，其实上面的逻辑自己走一边就通了</p>
<p><strong>解法二</strong></p>
<p>这个解法就带有点技巧性了，看懂上面的注释，下面的代码就很简单了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">// (()(())) = 2*()+2*(())= (())+((()))</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">scoreOfParentheses</span><span class="params">(String S)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> k=<span class="number">0</span>,res=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;S.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (S.charAt(i)==<span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">            k++; <span class="comment">//k用来计算括号的深度</span></span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            k--;</span><br><span class="line">            <span class="keyword">if</span> (S.charAt(i-<span class="number">1</span>)==<span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">                <span class="comment">//&quot;()&quot;闭合的时候计算一波</span></span><br><span class="line">                res+= <span class="number">1</span>&lt;&lt;k; <span class="comment">//2^k</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="946-验证栈序列"><a href="#946-验证栈序列" class="headerlink" title="946. 验证栈序列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/validate-stack-sequences/" >946. 验证栈序列<i class="fas fa-external-link-alt"></i></a></h2><p>给定 <code>pushed</code> 和 <code>popped</code> 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 <code>push</code> 和弹出 pop 操作序列的结果时，返回 <code>true</code> 否则，返回 <code>false</code> </p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：pushed = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>], popped = [<span class="number">4</span>,<span class="number">5</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">输出：<span class="keyword">true</span></span><br><span class="line">解释：我们可以按以下顺序执行：</span><br><span class="line">push(<span class="number">1</span>), push(<span class="number">2</span>), push(<span class="number">3</span>), push(<span class="number">4</span>), pop() -&gt; <span class="number">4</span>,</span><br><span class="line">push(<span class="number">5</span>), pop() -&gt; <span class="number">5</span>, pop() -&gt; <span class="number">3</span>, pop() -&gt; <span class="number">2</span>, pop() -&gt; <span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：pushed = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>], popped = [<span class="number">4</span>,<span class="number">3</span>,<span class="number">5</span>,<span class="number">1</span>,<span class="number">2</span>]</span><br><span class="line">输出：<span class="keyword">false</span></span><br><span class="line">解释：<span class="number">1</span> 不能在 <span class="number">2</span> 之前弹出。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>0 &lt;= pushed.length == popped.length &lt;= 1000</code></li>
<li><code>0 &lt;= pushed[i], popped[i] &lt; 1000</code></li>
<li><code>pushed</code> 是 <code>popped</code> 的排列</li>
</ol>
<p><strong>解法一</strong></p>
<p>直接用栈模拟，可惜没有bugfree…</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">validateStackSequences</span><span class="params">(<span class="keyword">int</span>[] pushed, <span class="keyword">int</span>[] popped)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(pushed==<span class="keyword">null</span> || pushed.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> popIndex=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> pushIndex=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//pushed = [1,2,3,4,5], popped = [4,5,3,2,1]</span></span><br><span class="line">    <span class="comment">//[1,2,3,4,5]      [4,3,5,1,2]</span></span><br><span class="line">    <span class="comment">//[1,0] [1,0]</span></span><br><span class="line">    <span class="keyword">while</span>(pushIndex&lt;pushed.length)&#123;</span><br><span class="line">        stack.push(pushed[pushIndex++]);</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty()&amp;&amp;popped[popIndex]==stack.peek())&#123;</span><br><span class="line">            stack.pop();</span><br><span class="line">            popIndex++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>每进一个元素就判断栈顶和出栈顺序的头是否相等，然后出栈，最后看栈中是否为空就ok</p>
<h2 id="NC560-打字"><a href="#NC560-打字" class="headerlink" title="NC560.打字"></a><a class="link"   target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/7819ebf1369044e5bee2f9848d9c6c72" >NC560.打字<i class="fas fa-external-link-alt"></i></a></h2><p>牛妹在练习打字，现在按照时间顺序给出牛妹按下的键（以字符串形式给出,’&lt;’代表回退backspace，其余字符均是牛妹打的字符，字符只包含小写字母与’&lt;’），牛妹想知道最后在屏幕上显示的文本内容是什么。<br>在文本内容为空的时候也可以按回退backspace（在这种情况下没有任何效果）。<br><strong>示例1</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;acv&lt;&quot;</span></span><br><span class="line">输出: <span class="string">&quot;ac&quot;</span></span><br><span class="line">说明:</span><br><span class="line">牛妹在打完<span class="string">&quot;acv&quot;</span>之后按了回退，所以最后是<span class="string">&quot;ac&quot;</span></span><br></pre></td></tr></table></figure>
<p><strong>解法一</strong></p>
<p>也可以直接数组模拟</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">Typing</span> <span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// write code here</span></span><br><span class="line">    Deque&lt;Integer&gt; stack = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s.length(); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i) == <span class="string">&#x27;&lt;&#x27;</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (stack.isEmpty()) &#123;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            stack.pop();</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    StringBuilder sb = <span class="keyword">new</span> StringBuilder();</span><br><span class="line">    <span class="keyword">while</span>(!stack.isEmpty())&#123;</span><br><span class="line">        sb.append(s.charAt(stack.pop()));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sb.reverse().toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="BFS广搜"><a href="#BFS广搜" class="headerlink" title="BFS广搜"></a><em>BFS广搜</em></h2><h2 id="279-完全平方数"><a href="#279-完全平方数" class="headerlink" title="279. 完全平方数"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/perfect-squares/" >279. 完全平方数<i class="fas fa-external-link-alt"></i></a></h2><p>给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: n = <span class="number">12</span></span><br><span class="line">输出: <span class="number">3</span> </span><br><span class="line">解释: <span class="number">12</span> = <span class="number">4</span> + <span class="number">4</span> + <span class="number">4.</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: n = <span class="number">13</span></span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">解释: <span class="number">13</span> = <span class="number">4</span> + <span class="number">9.</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这题在上一篇<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/">dp专题</a>中有讲过，不过是dp的解法，这里主要记录BFS的解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">numSquares2</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[n+<span class="number">1</span>];</span><br><span class="line">    queue.add(<span class="keyword">new</span> Pair(n,<span class="number">0</span>));</span><br><span class="line">    visit[n]=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        <span class="keyword">int</span> num=pair.num;</span><br><span class="line">        <span class="keyword">int</span> step=pair.step;</span><br><span class="line">        <span class="comment">//nums=0说明找到了，并且一定是最短的</span></span><br><span class="line">        <span class="keyword">if</span> (num==<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> step;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i*i&lt;=num;i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> temp=num-i*i;</span><br><span class="line">            <span class="comment">//注意不要添加重复的元素</span></span><br><span class="line">            <span class="keyword">if</span> (!visit[temp]) &#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(temp,step+<span class="number">1</span>));</span><br><span class="line">                visit[temp]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span> step;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span> num;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> num,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.num=num;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>30ms 90%，比dp的方式会快很多，思路就是将这个问题转换为求图的最短路径的问题，找到一个最短的从n到0的以平方数为差的路径</p>
<h2 id="127-单词接龙"><a href="#127-单词接龙" class="headerlink" title="127. 单词接龙"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-ladder/" >127. 单词接龙<i class="fas fa-external-link-alt"></i></a></h2><p>Given two words (<em>beginWord</em> and <em>endWord</em>), and a dictionary’s word list, find the length of shortest transformation sequence from <em>beginWord</em> to <em>endWord</em>, such that:</p>
<ol>
<li>Only one letter can be changed at a time.</li>
<li>Each transformed word must exist in the word list. Note that <em>beginWord</em> is <em>not</em> a transformed word.</li>
</ol>
<p><strong>Note:</strong></p>
<ul>
<li>Return 0 if there is no such transformation sequence.</li>
<li>All words have the same length.</li>
<li>All words contain only lowercase alphabetic characters.</li>
<li>You may assume no duplicates in the word list.</li>
<li>You may assume <em>beginWord</em> and <em>endWord</em> are non-empty and are not the same.</li>
</ul>
<p><strong>Example 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input:</span><br><span class="line">beginWord = <span class="string">&quot;hit&quot;</span>,</span><br><span class="line">endWord = <span class="string">&quot;cog&quot;</span>,</span><br><span class="line">wordList = [<span class="string">&quot;hot&quot;</span>,<span class="string">&quot;dot&quot;</span>,<span class="string">&quot;dog&quot;</span>,<span class="string">&quot;lot&quot;</span>,<span class="string">&quot;log&quot;</span>,<span class="string">&quot;cog&quot;</span>]</span><br><span class="line"></span><br><span class="line">Output: <span class="number">5</span></span><br><span class="line"></span><br><span class="line">Explanation: As one shortest transformation is <span class="string">&quot;hit&quot;</span> -&gt; <span class="string">&quot;hot&quot;</span> -&gt; <span class="string">&quot;dot&quot;</span> -&gt; <span class="string">&quot;dog&quot;</span> -&gt; <span class="string">&quot;cog&quot;</span>,</span><br><span class="line"><span class="keyword">return</span> its length <span class="number">5.</span></span><br></pre></td></tr></table></figure>

<p><strong>Example 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input:</span><br><span class="line">beginWord = <span class="string">&quot;hit&quot;</span></span><br><span class="line">endWord = <span class="string">&quot;cog&quot;</span></span><br><span class="line">wordList = [<span class="string">&quot;hot&quot;</span>,<span class="string">&quot;dot&quot;</span>,<span class="string">&quot;dog&quot;</span>,<span class="string">&quot;lot&quot;</span>,<span class="string">&quot;log&quot;</span>]</span><br><span class="line"></span><br><span class="line">Output: <span class="number">0</span></span><br><span class="line"></span><br><span class="line">Explanation: The endWord <span class="string">&quot;cog&quot;</span> is not in wordList, therefore no possible transformation.</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这题其实很久以前就写过了，当时是看了啊哈算法的一些BFS算法然后仿照书上的写的，书上是C语言写的，所以最后我写的时候也按照C的格式去写了😅，写的贼啰嗦，现在又用”Java”的方式又重新写了一遍</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span>[] mark;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> min = Integer.MAX_VALUE;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">ladderLength</span><span class="params">(String beginWord, String endWord, List&lt;String&gt; wordList)</span>     </span>&#123;</span><br><span class="line">    <span class="comment">// 不存在</span></span><br><span class="line">    mark = <span class="keyword">new</span> <span class="keyword">int</span>[wordList.size() + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">if</span> (!wordList.contains(endWord)) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// BFS</span></span><br><span class="line">    <span class="keyword">int</span> head = <span class="number">0</span>, tail = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 初始化队列</span></span><br><span class="line">    Que[] que = <span class="keyword">new</span> Que[wordList.size() + <span class="number">1</span>];</span><br><span class="line">    <span class="comment">// 循环促使话述祖</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; que.length; i++) &#123;</span><br><span class="line">        que[i] = <span class="keyword">new</span> Que();</span><br><span class="line">    &#125;</span><br><span class="line">    que[tail].word = beginWord;</span><br><span class="line">    que[tail].step = <span class="number">1</span>;</span><br><span class="line">    tail++;</span><br><span class="line">    <span class="keyword">int</span> flag=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (head &lt; tail) &#123;</span><br><span class="line">        <span class="comment">// 遍历字典</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; wordList.size(); i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (mark[i] == <span class="number">0</span> &amp;&amp; cmp(wordList.get(i), que[head].word)) &#123;</span><br><span class="line">                que[tail].word = wordList.get(i);</span><br><span class="line">                <span class="comment">//这里是从head开始的，所以应该是head的步数+1</span></span><br><span class="line">                que[tail].step=que[head].step+<span class="number">1</span>;</span><br><span class="line">                <span class="comment">// 标记为已经走过</span></span><br><span class="line">                mark[i] = <span class="number">1</span>;</span><br><span class="line">                <span class="comment">// 统计最小步数</span></span><br><span class="line">               <span class="keyword">if</span> (que[tail].word.equals(endWord)) &#123;</span><br><span class="line">                <span class="comment">//跳出循环</span></span><br><span class="line">                    flag=<span class="number">1</span>;</span><br><span class="line">                   <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                tail++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(flag==<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 每次检查完一个单词就将其出队列</span></span><br><span class="line">        head++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> que[tail].step;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 写一个函数判段没吃是否只变化了一个字母</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">cmp</span><span class="params">(String s1, String s2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s1.length(); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s1.charAt(i) != s2.charAt(i)) &#123;</span><br><span class="line">            count++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count == <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 内部类</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Que</span> </span>&#123;</span><br><span class="line">    String word;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这就是当时写的解法，思路就是BFS，只不过写的复杂了</p>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">ladderLength</span><span class="params">(String beginWord, String endWord, List&lt;String&gt; wordList)</span>     </span>&#123;</span><br><span class="line">    <span class="comment">//visit数组</span></span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[wordList.size()];</span><br><span class="line">    <span class="keyword">if</span> (!wordList.contains(endWord)) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    queue.add(<span class="keyword">new</span> Pair(beginWord,<span class="number">1</span>));</span><br><span class="line">    <span class="comment">//int flag=0;</span></span><br><span class="line">    <span class="keyword">while</span> (!queue.isEmpty()) &#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        <span class="comment">// 统计最小步数,放在内循环中会快一点</span></span><br><span class="line">        <span class="comment">/*if (pair.word.equals(endWord)) &#123;</span></span><br><span class="line"><span class="comment">            return pair.step;</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">        <span class="comment">// 遍历字典</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; wordList.size(); i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!visit[i] &amp;&amp; cmp(wordList.get(i),pair.word)) &#123;</span><br><span class="line">                <span class="keyword">if</span> (wordList.get(i).equals(endWord)) &#123;</span><br><span class="line">                    <span class="comment">//这里加1 是因为取的是pair的step</span></span><br><span class="line">                    <span class="comment">//到当前这个单词还要多走一步</span></span><br><span class="line">                    <span class="keyword">return</span> pair.step+<span class="number">1</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(wordList.get(i),pair.step+<span class="number">1</span>));</span><br><span class="line">                <span class="comment">//标记为已经走过</span></span><br><span class="line">                visit[i] = <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//是否只变化了一个字符</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">cmp</span><span class="params">(String s1, String s2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s1.length(); i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s1.charAt(i) != s2.charAt(i)) &#123;</span><br><span class="line">            count++;</span><br><span class="line">            <span class="keyword">if</span> (count&gt;<span class="number">1</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count == <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//Pair</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span> </span>&#123;</span><br><span class="line">    String word;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(String word,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.word=word;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>273ms，47%中规中矩的做法，连续写了好几题BFS的，总算是对BFS的板子有点熟悉了，这题还有两个可以优化的点 ① <em>双端BFS</em> ② _寻找下一个字符串的方式_，只不过我没咋看懂，等看懂了再来补充，那种方式时间好像可以缩减到 20ms内…..</p>
<blockquote>
<p>这题有个困难版本，需要打印出所有的最短序列，这个在我很久之前的一篇文章中也有讲，但是至今我也还没有AC，一直是TLE，现在回头看我之前的代码已经看不懂了。。。写了100多行，略复杂BFS+DFS的做法，可能是没处理好所以TLE了，感兴趣可以看看<a href="http://imlgw.top/2018/10/31/yi-dao-leetcode-yin-fa-de-can-an/#2-%E5%8A%A0%E5%BC%BA%E7%89%88-%E5%8D%95%E8%AF%8D%E6%8E%A5%E9%BE%99-2">那篇文章</a></p>
</blockquote>
<h2 id="542-01-矩阵"><a href="#542-01-矩阵" class="headerlink" title="542. 01 矩阵"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/01-matrix/" >542. 01 矩阵<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。</p>
<p>两个相邻元素间的距离为 1 </p>
<p><strong>示例 1:</strong><br>输入:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br></pre></td></tr></table></figure>

<p>输出:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong><br>输入:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">0</span></span><br><span class="line"><span class="number">1</span> <span class="number">1</span> <span class="number">1</span></span><br></pre></td></tr></table></figure>


<p>输出:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">0</span></span><br><span class="line"><span class="number">1</span> <span class="number">2</span> <span class="number">1</span></span><br></pre></td></tr></table></figure>


<p><strong>注意:</strong></p>
<ul>
<li>给定矩阵的元素个数不超过 10000</li>
<li>给定矩阵中至少有一个元素是 0</li>
<li>矩阵中的元素只在四个方向上相邻: 上、下、左、右</li>
</ul>
<p><strong>解法一</strong></p>
<p>憨憨的BFS解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//遍历每一个1,BFS寻找离他最近的0,一次只能确定一个1,效率略低</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[][] updateMatrix(<span class="keyword">int</span>[][] matrix) &#123;</span><br><span class="line">    <span class="keyword">if</span> (matrix == <span class="keyword">null</span> || matrix.length &lt;=<span class="number">0</span> || matrix[<span class="number">0</span>].length &lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[][]&#123;&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;matrix.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;matrix[<span class="number">0</span>].length;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (matrix[i][j] == <span class="number">1</span>) &#123;</span><br><span class="line">                matrix[i][j]=findMinDis(matrix,i,j);   </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> matrix;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[][] direction=&#123;&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMinDis</span><span class="params">(<span class="keyword">int</span>[][] matrix,<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="comment">//boolean[][] visit=new boolean[matrix.length][matrix[0].length];</span></span><br><span class="line">    queue.add(<span class="keyword">new</span> Pair(x,y,<span class="number">0</span>));</span><br><span class="line">    <span class="comment">//visit[x][y]=true;</span></span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;direction.length;i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> nx=pair.x + direction[i][<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">int</span> ny=pair.y + direction[i][<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span> (isValid(matrix,nx,ny) <span class="comment">/*&amp;&amp; !visit[nx][ny]*/</span>) &#123;</span><br><span class="line">                <span class="comment">//visit[nx][ny]=true;</span></span><br><span class="line">                <span class="keyword">if</span> (matrix[nx][ny] == <span class="number">0</span>) &#123;</span><br><span class="line">                    <span class="keyword">return</span> pair.step+<span class="number">1</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(nx,ny,pair.step+<span class="number">1</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>; <span class="comment">//题目说了一定有0,所以不会走到这里</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isValid</span><span class="params">(<span class="keyword">int</span>[][] matrix,<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x&gt;=<span class="number">0</span> &amp;&amp; x&lt;matrix.length &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;matrix[<span class="number">0</span>].length;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> x;</span><br><span class="line">    <span class="keyword">int</span> y;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.x=x;</span><br><span class="line">        <span class="keyword">this</span>.y=y;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看到代码中有很明显的改动痕迹，最开始是用visit数组保证每一个元素只会进队列一次，不会重复的进队列，但是这里为什么我去掉了呢？</p>
<p>其实主要是一开始提交的解法超时了，把visit数组去掉就过了，在数组过大的时候每次BFS都要开辟一个matrix大小的boolean数组，这无疑会极其耗费时间，但是为什么不加visit数组不会死循环呢？</p>
<p>确实，如果不加visit数组那么确实是有可能会导致死循环的，两个节点互相重复添加对方，但是这一题有个很关键的地方，题目说明了一定会有0，也就是说一定会解，那么就不会死循环，举一个很简单的例子</p>
<p><code>【0，1，1】</code> 这里我们先考虑中间的1，然后我们按照下右上左的顺序去添加周围的节点，那么队列中就为末尾的<code>[1]</code> ，当遍历到右的时候发现是0，直接return，然后我们考虑下一个1，转了一圈队列中只有一个中间的<code>[1]</code> ， 然后我们又重复刚刚的步骤会将末尾的1又加入队列，但是下一次遍历就会找到最左边的0，然后返回，所以并不会死循环，当然这样做的前提是一定要有解！</p>
<p><strong>解法二</strong></p>
<p>另一种更好的做法，以0作为源，向四周BFS，同时更新周围的1的值</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//update: 2020.4.15</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[][] dir=&#123;&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[][] updateMatrix(<span class="keyword">int</span>[][] matrix) &#123;</span><br><span class="line">    <span class="keyword">if</span>(matrix==<span class="keyword">null</span> || matrix.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> matrix;</span><br><span class="line">    <span class="keyword">boolean</span>[][] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[matrix.length][matrix[<span class="number">0</span>].length];</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;matrix.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;matrix[<span class="number">0</span>].length;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(matrix[i][j]==<span class="number">0</span>)&#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(i,j,<span class="number">0</span>));</span><br><span class="line">                visit[i][j]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                matrix[i][j]=Integer.MAX_VALUE;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;dir.length;i++)&#123;</span><br><span class="line">            <span class="keyword">int</span> nx=pair.x+dir[i][<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">int</span> ny=pair.y+dir[i][<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span>(valid(matrix,nx,ny) &amp;&amp; !visit[nx][ny])&#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(nx,ny,pair.step+<span class="number">1</span>));</span><br><span class="line">                matrix[nx][ny]=pair.step+<span class="number">1</span>; <span class="comment">//这里不用判断是不是变小，第一次遇到的就是最近的</span></span><br><span class="line">                visit[nx][ny]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> matrix;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">valid</span><span class="params">(<span class="keyword">final</span> <span class="keyword">int</span>[][] matrix,<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x&gt;=<span class="number">0</span> &amp;&amp; x&lt;matrix.length &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;matrix[<span class="number">0</span>].length;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> x,y;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.x=x;</span><br><span class="line">        <span class="keyword">this</span>.y=y;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>核心思想就是 把所有1都置为最大值, 把所有为0的位置加入队列中, 每次从队列中poll 一个节点, 更新其四周的节点, <del>如果被更新的节点距离变小了就将其也加入队列准备更新其邻接点</del> step是递增的，第一次遇到的一定是最近的</p>
<p>多源BFS，参考下面的 <a href="">994. 腐烂的橘子</a>  和 <a href="">1162. 地图分析</a></p>
<p><strong>解法三</strong></p>
<blockquote>
<p>这题的最优解应该是动态规划的解法，我实在是懒得写（菜），其实和哪个 不同路径有点类似，每个1离他最近的0的距离其实就是它周围的元素离0最近的距离+1</p>
<p>也就是 <code>matrix[i][j] =min(dp[i][j-1],dp[i-1][j],dp[i+1][j],dp[i][j+1]) + 1</code> 但是我们不可能同时求出是个方向的最小值，所以我们需要两次遍历，第一遍从左上到右下，第二遍从右下到左上，两次遍历就可以确定每个节点的值，代码以后有时间再来写</p>
</blockquote>
<h2 id="1306-跳跃游戏-III"><a href="#1306-跳跃游戏-III" class="headerlink" title="1306. 跳跃游戏 III"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/jump-game-iii/" >1306. 跳跃游戏 III<i class="fas fa-external-link-alt"></i></a></h2><p>这里有一个非负整数数组 <code>arr</code>，你最开始位于该数组的起始下标 <code>start</code> 处。当你位于下标 i 处时，你可以跳到 <code>i + arr[i]</code> 或者 <code>i - arr[i]</code>。</p>
<p>请你判断自己是否能够跳到对应元素值为 0 的 <code>任意</code> 下标处。</p>
<p>注意，不管是什么情况下，你都无法跳到数组之外</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">4</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">1</span>,<span class="number">2</span>], start = <span class="number">5</span></span><br><span class="line">输出：<span class="keyword">true</span></span><br><span class="line">解释：</span><br><span class="line">到达值为 <span class="number">0</span> 的下标 <span class="number">3</span> 有以下可能方案： </span><br><span class="line">下标 <span class="number">5</span> -&gt; 下标 <span class="number">4</span> -&gt; 下标 <span class="number">1</span> -&gt; 下标 <span class="number">3</span> </span><br><span class="line">下标 <span class="number">5</span> -&gt; 下标 <span class="number">6</span> -&gt; 下标 <span class="number">4</span> -&gt; 下标 <span class="number">1</span> -&gt; 下标 <span class="number">3</span> </span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">4</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">1</span>,<span class="number">2</span>], start = <span class="number">0</span></span><br><span class="line">输出：<span class="keyword">true</span> </span><br><span class="line">解释：</span><br><span class="line">到达值为 <span class="number">0</span> 的下标 <span class="number">3</span> 有以下可能方案： </span><br><span class="line">下标 <span class="number">0</span> -&gt; 下标 <span class="number">4</span> -&gt; 下标 <span class="number">1</span> -&gt; 下标 <span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">3</span>,<span class="number">0</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">2</span>], start = <span class="number">2</span></span><br><span class="line">输出：<span class="keyword">false</span></span><br><span class="line">解释：无法到达值为 <span class="number">0</span> 的下标 <span class="number">1</span> 处。 </span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= arr.length &lt;= 5 * 10^4</code></li>
<li><code>0 &lt;= arr[i] &lt; arr.length</code></li>
<li><code>0 &lt;= start &lt; arr.length</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>BFS，某次周赛的第3题，还是挺简单的，可惜那次没参加</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canReach</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> start)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[arr.length];</span><br><span class="line">    Queue&lt;Integer&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    queue.add(start);</span><br><span class="line">    visit[start]=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">int</span> cur=queue.poll();</span><br><span class="line">        <span class="keyword">if</span> (arr[cur] == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (cur-arr[cur]&gt;=<span class="number">0</span> &amp;&amp; !visit[cur-arr[cur]]) &#123;</span><br><span class="line">            queue.add(cur-arr[cur]);</span><br><span class="line">            visit[cur-arr[cur]]=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (cur+arr[cur]&lt;arr.length &amp;&amp; !visit[cur+arr[cur]]) &#123;</span><br><span class="line">            queue.add(cur+arr[cur]);</span><br><span class="line">            visit[cur+arr[cur]]=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>DFS解法，没啥好说的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canReach</span><span class="params">(<span class="keyword">int</span>[] arr,<span class="keyword">int</span> start)</span></span>&#123;</span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[arr.length];</span><br><span class="line">    <span class="keyword">return</span> dfs(arr,start,visit);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span>[] arr,<span class="keyword">int</span> index,<span class="keyword">boolean</span>[] visit)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr[index] == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    visit[index]=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">boolean</span> b=<span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">if</span> (index-arr[index] &gt;=<span class="number">0</span> &amp;&amp; !visit[index-arr[index]]) &#123;</span><br><span class="line">        b=dfs(arr,index-arr[index],visit);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (index+arr[index] &lt;arr.length &amp;&amp; !visit[index+arr[index]]) &#123;</span><br><span class="line">        <span class="keyword">return</span> b|dfs(arr,index+arr[index],visit);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> b;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="5314-跳跃游戏-IV"><a href="#5314-跳跃游戏-IV" class="headerlink" title="5314. 跳跃游戏 IV"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/jump-game-iv/" >5314. 跳跃游戏 IV<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。</p>
<p>每一步，你可以从下标 i 跳到下标：</p>
<ul>
<li>i + 1 满足：i + 1 &lt; arr.length</li>
<li>i - 1 满足：i - 1 &gt;= 0</li>
<li>j 满足：arr[i] == arr[j] 且 i != j</li>
</ul>
<p>请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。<br>注意：任何时候你都不能跳到数组外面。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">100</span>,-<span class="number">23</span>,-<span class="number">23</span>,<span class="number">404</span>,<span class="number">100</span>,<span class="number">23</span>,<span class="number">23</span>,<span class="number">23</span>,<span class="number">3</span>,<span class="number">404</span>]</span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释：那你需要跳跃 <span class="number">3</span> 次，下标依次为 <span class="number">0</span> --&gt; <span class="number">4</span> --&gt; <span class="number">3</span> --&gt; <span class="number">9</span> 。下标 <span class="number">9</span> 为数组的最后一个元素的下标。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">7</span>]</span><br><span class="line">输出：<span class="number">0</span></span><br><span class="line">解释：一开始就在最后一个元素处，所以你不需要跳跃。</span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">7</span>,<span class="number">6</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">9</span>,<span class="number">7</span>]</span><br><span class="line">输出：<span class="number">1</span></span><br><span class="line">解释：你可以直接从下标 <span class="number">0</span> 处跳到下标 <span class="number">7</span> 处，也就是数组的最后一个元素处。</span><br></pre></td></tr></table></figure>


<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">6</span>,<span class="number">1</span>,<span class="number">9</span>]</span><br><span class="line">输出：<span class="number">2</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 5：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：arr = [<span class="number">11</span>,<span class="number">22</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">22</span>,<span class="number">13</span>]</span><br><span class="line">输出：<span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= arr.length &lt;= 5 * 10^4</code></li>
<li><code>-10^8 &lt;= arr[i] &lt;= 10^8</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>19双周赛的最后一题，讲道理挺简单的（可我还是TLE了好长时间）</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minJumps</span><span class="params">(<span class="keyword">int</span>[] arr)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[arr.length];</span><br><span class="line">    HashMap&lt;Integer,List&lt;Integer&gt;&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="comment">//构建等值的索引 连续相同的只保留头尾</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;arr.length;i++) &#123;</span><br><span class="line">        List&lt;Integer&gt; lis=map.computeIfAbsent(arr[i],k-&gt;<span class="keyword">new</span> ArrayList&lt;&gt;());</span><br><span class="line">        <span class="keyword">if</span> (!((i-<span class="number">1</span>&gt;=<span class="number">0</span>&amp;&amp;arr[i-<span class="number">1</span>]==arr[i]) &amp;&amp; (i+<span class="number">1</span>&lt;arr.length&amp;&amp;arr[i+<span class="number">1</span>]==arr[i])))&#123;</span><br><span class="line">            lis.add(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    queue.add(<span class="keyword">new</span> Pair(<span class="number">0</span>,<span class="number">0</span>));</span><br><span class="line">    visit[<span class="number">0</span>]=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        <span class="keyword">if</span> (pair.index==arr.length-<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> pair.step;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(pair.index+<span class="number">1</span>&lt;arr.length &amp;&amp; !visit[pair.index+<span class="number">1</span>])&#123;</span><br><span class="line">            queue.add(<span class="keyword">new</span> Pair(pair.index+<span class="number">1</span>,pair.step+<span class="number">1</span>));</span><br><span class="line">            visit[pair.index+<span class="number">1</span>]=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (pair.index-<span class="number">1</span>&gt;=<span class="number">0</span> &amp;&amp; !visit[pair.index-<span class="number">1</span>]) &#123;</span><br><span class="line">            queue.add(<span class="keyword">new</span> Pair(pair.index-<span class="number">1</span>,pair.step+<span class="number">1</span>));</span><br><span class="line">            visit[pair.index-<span class="number">1</span>]=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        List&lt;Integer&gt; list=map.get(arr[pair.index]);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=list.size()-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--) &#123;</span><br><span class="line">            <span class="keyword">int</span> idx=list.get(i);</span><br><span class="line">            <span class="keyword">if</span> (!visit[idx]) &#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(idx,pair.step+<span class="number">1</span>));</span><br><span class="line">                visit[idx]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> index;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> index,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.index=index;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>看一下数据范围，直接BFS遍历跳同值的肯定不行，所以想到了用map预处理同值的索引，结果还是TLE了，后面一个case有50000个7，这里即使做了map索引但是无奈太多了，依然会超时，这里其实这么多7，只有头和尾的7是用的，其他位置的7都是无用的，可以直接忽略，所以构建索引的时候可以跳过这些中间位置，这样可以节省很多时间</p>
<h2 id="690-员工的重要性"><a href="#690-员工的重要性" class="headerlink" title="690. 员工的重要性"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/employee-importance/" >690. 员工的重要性<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。</p>
<p>比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。</p>
<p>现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>, <span class="number">5</span>, [<span class="number">2</span>, <span class="number">3</span>]], [<span class="number">2</span>, <span class="number">3</span>, []], [<span class="number">3</span>, <span class="number">3</span>, []]], <span class="number">1</span></span><br><span class="line">输出: <span class="number">11</span></span><br><span class="line">解释:</span><br><span class="line">员工<span class="number">1</span>自身的重要度是<span class="number">5</span>，他有两个直系下属<span class="number">2</span>和<span class="number">3</span>，而且<span class="number">2</span>和<span class="number">3</span>的重要度均为<span class="number">3</span>。因此员工<span class="number">1</span>的总重要度是 <span class="number">5</span> + <span class="number">3</span> + <span class="number">3</span> = <span class="number">11</span>。</span><br></pre></td></tr></table></figure>


<p><strong>注意:</strong></p>
<ol>
<li>一个员工最多有一个直系领导，但是可以有多个直系下属</li>
<li>员工数量不超过2000。</li>
</ol>
<p><strong>解法一</strong></p>
<p>BFS，没啥好说的，憨憨题直接bugfree</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getImportance</span><span class="params">(List&lt;Employee&gt; employees, <span class="keyword">int</span> id)</span> </span>&#123;</span><br><span class="line">    HashMap&lt;Integer,Employee&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (Employee e:employees) &#123;</span><br><span class="line">        map.put(e.id,e);</span><br><span class="line">    &#125;</span><br><span class="line">    Queue&lt;Integer&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    queue.add(id);</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Employee cur=map.get(queue.poll());</span><br><span class="line">        res+=cur.importance;</span><br><span class="line">        List&lt;Integer&gt; subordinates=cur.subordinates;</span><br><span class="line">        <span class="keyword">if</span> (!subordinates.isEmpty()) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> eid:subordinates) &#123;</span><br><span class="line">                queue.add(eid);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>DFS，本来不想写的，这类题其实都是树的题变了个说法而已</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getImportance</span><span class="params">(List&lt;Employee&gt; employees, <span class="keyword">int</span> id)</span> </span>&#123;</span><br><span class="line">    HashMap&lt;Integer,Employee&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (Employee e:employees) &#123;</span><br><span class="line">        map.put(e.id,e);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dfs(map,id);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">dfs</span><span class="params">(HashMap&lt;Integer,Employee&gt; map,<span class="keyword">int</span> id)</span></span>&#123;</span><br><span class="line">    Employee cur=map.get(id);</span><br><span class="line">    <span class="keyword">int</span> res=cur.importance;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> eid:cur.subordinates) &#123;</span><br><span class="line">        res+=dfs(map,eid);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="1311-获取你好友已观看的视频"><a href="#1311-获取你好友已观看的视频" class="headerlink" title="1311. 获取你好友已观看的视频"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/get-watched-videos-by-your-friends/" >1311. 获取你好友已观看的视频<i class="fas fa-external-link-alt"></i></a></h2><p>有 n 个人，每个人都有一个  0 到 n-1 的唯一 id 。</p>
<p>给你数组 <code>watchedVideos</code>  和 <code>friends</code> ，其中 <code>watchedVideos[i]</code>  和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。</p>
<p>Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。</p>
<p>给定你的 <code>id</code>  和一个 <code>level</code> 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按名字字典序从小到大排列。</p>
<p><strong>示例 1：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2020/02/01/I5XJKQg3WwvaeB1.png"
                      alt="image.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：watchedVideos = [[<span class="string">&quot;A&quot;</span>,<span class="string">&quot;B&quot;</span>],[<span class="string">&quot;C&quot;</span>],[<span class="string">&quot;B&quot;</span>,<span class="string">&quot;C&quot;</span>],[<span class="string">&quot;D&quot;</span>]], friends = [[<span class="number">1</span>,<span class="number">2</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">1</span>,<span class="number">2</span>]], id = <span class="number">0</span>, level = <span class="number">1</span></span><br><span class="line">输出：[<span class="string">&quot;B&quot;</span>,<span class="string">&quot;C&quot;</span>] </span><br><span class="line">解释：</span><br><span class="line">你的 id 为 <span class="number">0</span> ，你的朋友包括：</span><br><span class="line">id 为 <span class="number">1</span> -&gt; watchedVideos = [<span class="string">&quot;C&quot;</span>] </span><br><span class="line">id 为 <span class="number">2</span> -&gt; watchedVideos = [<span class="string">&quot;B&quot;</span>,<span class="string">&quot;C&quot;</span>] </span><br><span class="line">你朋友观看过视频的频率为：</span><br><span class="line">B -&gt; <span class="number">1</span> </span><br><span class="line">C -&gt; <span class="number">2</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2020/02/01/qhDZvr3sbJkgIuw.png"
                      alt="image.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：watchedVideos = [[<span class="string">&quot;A&quot;</span>,<span class="string">&quot;B&quot;</span>],[<span class="string">&quot;C&quot;</span>],[<span class="string">&quot;B&quot;</span>,<span class="string">&quot;C&quot;</span>],[<span class="string">&quot;D&quot;</span>]], friends = [[<span class="number">1</span>,<span class="number">2</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">1</span>,<span class="number">2</span>]], id = <span class="number">0</span>, level = <span class="number">2</span></span><br><span class="line">输出：[<span class="string">&quot;D&quot;</span>]</span><br><span class="line">解释：</span><br><span class="line">你的 id 为 <span class="number">0</span> ，你朋友的朋友只有一个人，他的 id 为 <span class="number">3</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>n == watchedVideos.length == friends.length</li>
<li>2 &lt;= n &lt;= 100</li>
<li>1 &lt;= watchedVideos[i].length &lt;= 100</li>
<li>1 &lt;= watchedVideos[i][j].length &lt;= 8</li>
<li>0 &lt;= friends[i].length &lt; n</li>
<li>0 &lt;= friends[i][j] &lt; n</li>
<li>0 &lt;= id &lt; n</li>
<li>1 &lt;= level &lt; n</li>
<li>如果 friends[i] 包含 j ，那么 friends[j] 包含 i</li>
</ul>
<p><strong>解法一</strong></p>
<p>170周赛的第三题，其实是一道水题，题目意思搞清楚就很简单了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> List&lt;String&gt; <span class="title">watchedVideosByFriends</span><span class="params">(List&lt;List&lt;String&gt;&gt; watchedVideos, <span class="keyword">int</span>[][] friends, <span class="keyword">int</span> id, <span class="keyword">int</span> level)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Integer&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span>[] levels=<span class="keyword">new</span> <span class="keyword">int</span>[friends.length]; <span class="comment">//这里没必要,这里用一个变量就ok了</span></span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[friends.length];</span><br><span class="line">    HashMap&lt;String,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    List&lt;Integer&gt; flist=<span class="keyword">new</span> ArrayList&lt;&gt;(); <span class="comment">//level层的朋友</span></span><br><span class="line">    queue.add(id);</span><br><span class="line">    visit[id]=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">int</span> cur=queue.poll();</span><br><span class="line">        <span class="keyword">int</span>[] cfs=friends[cur];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;cfs.length;i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!visit[cfs[i]]) &#123;</span><br><span class="line">                queue.add(cfs[i]);</span><br><span class="line">                levels[cfs[i]]=levels[cur]+<span class="number">1</span>;   </span><br><span class="line">                visit[cfs[i]]=<span class="keyword">true</span>;</span><br><span class="line">                <span class="keyword">if</span> (levels[cfs[i]] == level) &#123;</span><br><span class="line">                    flist.add(cfs[i]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;flist.size();i++) &#123;</span><br><span class="line">        List&lt;String&gt; videos=watchedVideos.get(flist.get(i));</span><br><span class="line">        <span class="keyword">for</span> (String v:videos) &#123;</span><br><span class="line">            map.put(v,map.getOrDefault(v,<span class="number">0</span>)+<span class="number">1</span>); <span class="comment">//map记录videos出现的次数</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//下面几步还是挺老道的</span></span><br><span class="line">    List&lt;String&gt; res=<span class="keyword">new</span> ArrayList(map.keySet());</span><br><span class="line">    res.sort((v1,v2)-&gt;&#123;</span><br><span class="line">        <span class="keyword">int</span> c1=map.get(v1);</span><br><span class="line">        <span class="keyword">int</span> c2=map.get(v2);</span><br><span class="line">        <span class="keyword">return</span> c1==c2?v1.compareTo(v2):c1-c2; <span class="comment">//相等的时候按照字典序列排序</span></span><br><span class="line">    &#125;);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="399-除法求值"><a href="#399-除法求值" class="headerlink" title="399. 除法求值"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/evaluate-division/" >399. 除法求值<i class="fas fa-external-link-alt"></i></a></h2><p>给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。</p>
<p>示例 :</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">给定 a / b = <span class="number">2.0</span>, b / c = <span class="number">3.0</span></span><br><span class="line">问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? </span><br><span class="line">返回 [<span class="number">6.0</span>, <span class="number">0.5</span>, -<span class="number">1.0</span>, <span class="number">1.0</span>, -<span class="number">1.0</span> ]</span><br></pre></td></tr></table></figure>

<p>输入为: <code>vector&lt;pair&lt;string, string&gt;&gt; equations, vector&lt;double&gt;&amp; values, vector&lt;pair&lt;string, string&gt;&gt; queries(方程式，方程式结果，问题方程式)</code>， 其中 <code>equations.size() == values.size()</code>，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回<code>vector&lt;double&gt;</code>类型。</p>
<p>基于上述例子，输入如下：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">equations(方程式) = [ [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;b&quot;</span>], [<span class="string">&quot;b&quot;</span>, <span class="string">&quot;c&quot;</span>] ],</span><br><span class="line">values(方程式结果) = [<span class="number">2.0</span>, <span class="number">3.0</span>],</span><br><span class="line">queries(问题方程式) = [ [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;c&quot;</span>], [<span class="string">&quot;b&quot;</span>, <span class="string">&quot;a&quot;</span>], [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;e&quot;</span>], [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;a&quot;</span>], [<span class="string">&quot;x&quot;</span>, <span class="string">&quot;x&quot;</span>] ]. </span><br></pre></td></tr></table></figure>

<p>输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。</p>
<p><strong>解法一</strong></p>
<p>建立图，然后BFS，这样就简单多了，比并茶集的方法直白多了，随便也学了一下如何建图</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//构造图 + BFS/DFS</span></span><br><span class="line"><span class="keyword">private</span> Map&lt;String,Map&lt;String,Double&gt;&gt; graph = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">buildGraph</span><span class="params">(List&lt;List&lt;String&gt;&gt; equations, <span class="keyword">double</span>[] values)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; values.length; i++) &#123;</span><br><span class="line">        graph.computeIfAbsent(equations.get(i).get(<span class="number">0</span>), k -&gt; <span class="keyword">new</span> HashMap&lt;&gt;()).put(equations.get(i).get(<span class="number">1</span>), values[i]);</span><br><span class="line">        graph.computeIfAbsent(equations.get(i).get(<span class="number">1</span>), k -&gt; <span class="keyword">new</span> HashMap&lt;&gt;()).put(equations.get(i).get(<span class="number">0</span>), <span class="number">1</span> / values[i]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    String key;</span><br><span class="line">    <span class="keyword">double</span> val;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(String key,<span class="keyword">double</span> val)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.key=key;</span><br><span class="line">        <span class="keyword">this</span>.val=val;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">double</span> <span class="title">bfs</span><span class="params">(String a,String b)</span></span>&#123;</span><br><span class="line">    <span class="comment">//讲道理,不管a,b是否在graph中,只要想等都应该返回1吧,这里是考虑了0的情况?</span></span><br><span class="line">    <span class="keyword">if</span> (!graph.containsKey(a) || !graph.containsKey(b)) &#123;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1.0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (a.equals(b)) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1.0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    queue.add(<span class="keyword">new</span> Pair(a,<span class="number">1.0</span>));</span><br><span class="line">    HashSet&lt;String&gt; visit=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair cur=queue.poll();</span><br><span class="line">        <span class="keyword">if</span> (!visit.contains(cur.key)) &#123;</span><br><span class="line">            visit.add(cur.key);</span><br><span class="line">            Map&lt;String,Double&gt; map=graph.get(cur.key);</span><br><span class="line">            <span class="keyword">for</span> (String next:map.keySet()) &#123;</span><br><span class="line">                <span class="keyword">if</span> (b.equals(next)) &#123;</span><br><span class="line">                    <span class="keyword">return</span> cur.val*map.get(next);</span><br><span class="line">                &#125;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(next,cur.val*map.get(next)));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1.0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">double</span> <span class="title">dfs</span><span class="params">(String a,String b,HashSet&lt;String&gt; visit)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!graph.containsKey(a)) &#123;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (a.equals(b)) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    visit.add(a);</span><br><span class="line">    Map&lt;String,Double&gt; nextMap=graph.get(a);</span><br><span class="line">    <span class="keyword">for</span> (String next:nextMap.keySet()) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!visit.contains(next)) &#123;</span><br><span class="line">            <span class="keyword">double</span> subres=dfs(next,b,visit);</span><br><span class="line">            <span class="keyword">if</span> (subres!=-<span class="number">1</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> subres*nextMap.get(next);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">double</span>[] calcEquation(List&lt;List&lt;String&gt;&gt; equations, <span class="keyword">double</span>[] values, List&lt;List&lt;String&gt;&gt; queries) &#123;</span><br><span class="line">    buildGraph(equations,values);</span><br><span class="line">    <span class="keyword">double</span>[] res=<span class="keyword">new</span> <span class="keyword">double</span>[queries.size()];</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (List&lt;String&gt; query:queries) &#123;</span><br><span class="line">        HashSet&lt;String&gt; visit=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">        <span class="comment">//res[index++]=bfs(query.get(0),query.get(1),visit); </span></span><br><span class="line">        res[index++]=bfs(query.get(<span class="number">0</span>),query.get(<span class="number">1</span>));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="301-删除无效的括号"><a href="#301-删除无效的括号" class="headerlink" title="301. 删除无效的括号"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-invalid-parentheses/" >301. 删除无效的括号<i class="fas fa-external-link-alt"></i></a></h2><p>删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。</p>
<p><strong>说明:</strong> 输入可能包含了除 ( 和 ) 以外的字符。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;()())()&quot;</span></span><br><span class="line">输出: [<span class="string">&quot;()()()&quot;</span>, <span class="string">&quot;(())()&quot;</span>]</span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;(a)())()&quot;</span></span><br><span class="line">输出: [<span class="string">&quot;(a)()()&quot;</span>, <span class="string">&quot;(a())()&quot;</span>]</span><br></pre></td></tr></table></figure>


<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;)(&quot;</span></span><br><span class="line">输出: [<span class="string">&quot;&quot;</span>]</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>BFS解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> List&lt;String&gt; <span class="title">removeInvalidParentheses</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    List&lt;String&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    Queue&lt;String&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    HashSet&lt;String&gt; visit=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    visit.add(s);</span><br><span class="line">    queue.add(s);</span><br><span class="line">    <span class="keyword">boolean</span> flag=<span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        String cur=queue.poll();</span><br><span class="line">        <span class="keyword">if</span> (isValid(cur)) &#123;</span><br><span class="line">            res.add(cur);</span><br><span class="line">            flag=<span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (flag) &#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;cur.length();i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (cur.charAt(i)==<span class="string">&#x27;(&#x27;</span> || cur.charAt(i)==<span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">                String temp=cur.substring(<span class="number">0</span>,i)+cur.substring(i+<span class="number">1</span>,cur.length());</span><br><span class="line">                <span class="keyword">if</span> (!visit.contains(temp)) &#123;</span><br><span class="line">                    queue.add(temp);</span><br><span class="line">                    visit.add(temp);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(res.isEmpty()) res.add(<span class="string">&quot;&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isValid</span><span class="params">(String s)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (s.charAt(i)==<span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">            left++;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (s.charAt(i)==<span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (left&gt;<span class="number">0</span>) &#123;</span><br><span class="line">                left--;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> left==<span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>还是比较简单，dfs的解法比较难搞，容易TLE，这里懒得写了</p>
<h2 id="994-腐烂的橘子"><a href="#994-腐烂的橘子" class="headerlink" title="994. 腐烂的橘子"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/rotting-oranges/" >994. 腐烂的橘子<i class="fas fa-external-link-alt"></i></a></h2><p>在给定的网格中，每个单元格可以有以下三个值之一：</p>
<ul>
<li>值 0 代表空单元格；</li>
<li>值 1 代表新鲜橘子；</li>
<li>值 2 代表腐烂的橘子。</li>
</ul>
<p>每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。</p>
<p>返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。</p>
<p><strong>示例 1：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200304/YGBajce2liDs.png?imageslim"
                      alt="mark"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>],[<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>],[<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>]]</span><br><span class="line">输出：-<span class="number">1</span></span><br><span class="line">解释：左下角的橘子（第 <span class="number">2</span> 行， 第 <span class="number">0</span> 列）永远不会腐烂，因为腐烂只会发生在 <span class="number">4</span> 个正向上。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">0</span>,<span class="number">2</span>]]</span><br><span class="line">输出：<span class="number">0</span></span><br><span class="line">解释：因为 <span class="number">0</span> 分钟时已经没有新鲜橘子了，所以答案就是 <span class="number">0</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= grid.length &lt;= 10</code></li>
<li><code>1 &lt;= grid[0].length &lt;= 10</code></li>
<li><code>grid[i][j]</code> 仅为 <code>0</code>、<code>1</code> 或 <code>2</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>BFS打卡题，这种解法应该算是比较好的了，2ms</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[][] diretion=&#123;&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">orangesRotting</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> time=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;grid.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;grid[<span class="number">0</span>].length;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="number">1</span>) count++; <span class="comment">//统计好橘子的数量</span></span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="number">2</span>)&#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(i,j));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(count==<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="comment">//每一轮的坏橘子数量</span></span><br><span class="line">        <span class="keyword">int</span> size=queue.size();</span><br><span class="line">        time++;</span><br><span class="line">        <span class="keyword">while</span>(size-- &gt;<span class="number">0</span>)&#123;</span><br><span class="line">            Pair pair=queue.poll();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;i++) &#123;</span><br><span class="line">                <span class="keyword">int</span> nx=pair.x+diretion[i][<span class="number">0</span>];</span><br><span class="line">                <span class="keyword">int</span> ny=pair.y+diretion[i][<span class="number">1</span>];</span><br><span class="line">                <span class="keyword">if</span>(valid(grid,nx,ny) &amp;&amp; grid[nx][ny]==<span class="number">1</span>)&#123;</span><br><span class="line">                    grid[nx][ny]=<span class="number">2</span>;</span><br><span class="line">                    count--;<span class="comment">//好橘子--</span></span><br><span class="line">                    queue.add(<span class="keyword">new</span> Pair(nx,ny));</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(count==<span class="number">0</span>) <span class="keyword">return</span> time;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> x,y;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.x=x;</span><br><span class="line">        <span class="keyword">this</span>.y=y;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">valid</span><span class="params">(<span class="keyword">final</span> <span class="keyword">int</span>[][] grid,<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x&gt;=<span class="number">0</span> &amp;&amp; x&lt;grid.length &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;grid[<span class="number">0</span>].length;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>一开始的解法，虽然效率稍微低一点点 4ms，但是bugfree了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[][] diretion=&#123;&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> x,y;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.x=x;</span><br><span class="line">        <span class="keyword">this</span>.y=y;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">orangesRotting</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>&#123;</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> max=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;grid.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;grid[<span class="number">0</span>].length;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="number">2</span>)&#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(i,j,<span class="number">0</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        <span class="comment">//统计一个最大的步数作为结果</span></span><br><span class="line">        <span class="comment">//max=Math.max(max,pair.step);</span></span><br><span class="line">        max=pair.step; <span class="comment">//最后弹出的哪个就是最大的，这是个递增(非单调)的过程</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> nx=pair.x+diretion[i][<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">int</span> ny=pair.y+diretion[i][<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span>(valid(grid,nx,ny) &amp;&amp; grid[nx][ny]==<span class="number">1</span>)&#123;</span><br><span class="line">                grid[nx][ny]=<span class="number">2</span>;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(nx,ny,pair.step+<span class="number">1</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> check(grid)?max:-<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">check</span><span class="params">(<span class="keyword">int</span>[][] grid)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;grid.length;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;grid[<span class="number">0</span>].length;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="number">1</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">valid</span><span class="params">(<span class="keyword">final</span> <span class="keyword">int</span>[][] grid,<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x&gt;=<span class="number">0</span> &amp;&amp; x&lt;grid.length &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;grid[<span class="number">0</span>].length;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>经过勘误，发现有一处地方有点小问题，已经修改，<code>pair.step</code> 在队列中是一个递增（不单调，会相等）的过程，所以最后弹出的就是最大的</p>
<h2 id="1162-地图分析"><a href="#1162-地图分析" class="headerlink" title="1162. 地图分析"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/as-far-from-land-as-possible/" >1162. 地图分析<i class="fas fa-external-link-alt"></i></a></h2><p>你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。</p>
<p>我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。</p>
<p>如果我们的地图上只有陆地或者海洋，请返回 -1。</p>
<p><strong>示例 1：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://s1.ax1x.com/2020/03/29/GVuO3Q.png"
                      alt="GVuO3Q.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],[<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">2</span></span><br><span class="line">解释： </span><br><span class="line">海洋区域 (<span class="number">1</span>, <span class="number">1</span>) 和所有陆地区域之间的距离都达到最大，最大距离为 <span class="number">2</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://s1.ax1x.com/2020/03/29/GVKSH0.png"
                      alt="GVKSH0.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]]</span><br><span class="line">输出：<span class="number">4</span></span><br><span class="line">解释： </span><br><span class="line">海洋区域 (<span class="number">2</span>, <span class="number">2</span>) 和所有陆地区域之间的距离都达到最大，最大距离为 <span class="number">4</span>。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= grid.length == grid[0].length &lt;= 100</code></li>
<li><code>grid[i][j]</code> 不是 <code>0</code> 就是 <code>1</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>这题的意思其实求<strong>离陆地最远的海洋是那一块，然后返回这个最远的距离</strong>，这个题目描述的确实让人迷惑，一会儿最远，一会儿最近，其实题目意思搞懂了就很简单了，其实和上面腐烂的橘子是一样的。多源的BFS，曼哈顿距离其实就是上下左右走的step</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[][] diretion=&#123;&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxDistance</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> maxDis=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> m=grid.length,n=grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">boolean</span>[][] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[m][n];</span><br><span class="line">    Queue&lt;Pair&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="number">1</span>)&#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(i,j,<span class="number">0</span>));</span><br><span class="line">                visit[i][j]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(queue.size()==<span class="number">0</span> || queue.size()==m*n)<span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> step=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> res=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        Pair pair=queue.poll();</span><br><span class="line">        res=pair.step;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;i++) &#123;</span><br><span class="line">            <span class="keyword">int</span> nx=pair.x+diretion[i][<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">int</span> ny=pair.y+diretion[i][<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span>(valid(grid,nx,ny) &amp;&amp; !visit[nx][ny] &amp;&amp; grid[nx][ny]==<span class="number">0</span>)&#123;</span><br><span class="line">                queue.add(<span class="keyword">new</span> Pair(nx,ny,pair.step+<span class="number">1</span>));</span><br><span class="line">                visit[nx][ny]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> x,y;</span><br><span class="line">    <span class="keyword">int</span> step;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Pair</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> step)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.x=x;</span><br><span class="line">        <span class="keyword">this</span>.y=y;</span><br><span class="line">        <span class="keyword">this</span>.step=step;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">valid</span><span class="params">(<span class="keyword">final</span> <span class="keyword">int</span>[][] grid,<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x&gt;=<span class="number">0</span> &amp;&amp; x&lt;grid.length &amp;&amp; y&gt;=<span class="number">0</span> &amp;&amp; y&lt;grid[<span class="number">0</span>].length;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="207-课程表"><a href="#207-课程表" class="headerlink" title="207. 课程表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/course-schedule/" >207. 课程表<i class="fas fa-external-link-alt"></i></a></h2><p>你这个学期必须选修 <code>numCourse</code> 门课程，记为 0 到 <code>numCourse-1</code> 。</p>
<p>在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：<code>[0,1]</code></p>
<p>给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">2</span>, [[<span class="number">1</span>,<span class="number">0</span>]] </span><br><span class="line">输出: <span class="keyword">true</span></span><br><span class="line">解释: 总共有 <span class="number">2</span> 门课程。学习课程 <span class="number">1</span> 之前，你需要完成课程 <span class="number">0</span>。所以这是可能的。</span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">2</span>, [[<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">1</span>]]</span><br><span class="line">输出: <span class="keyword">false</span></span><br><span class="line">解释: 总共有 <span class="number">2</span> 门课程。学习课程 <span class="number">1</span> 之前，你需要先完成课程 <span class="number">0</span>；并且学习课程 <span class="number">0</span> 之前，你还应先完成课程 <span class="number">1</span>。这是不可能的。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li>输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。</li>
<li>你可以假定输入的先决条件中没有重复的边。</li>
<li><code>1 &lt;= numCourses &lt;= 10^5</code></li>
</ol>
<p><strong>解法二</strong></p>
<p>学习下拓扑排序，其实核心在于邻接表的构建</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canFinish</span><span class="params">(<span class="keyword">int</span> numCourses, <span class="keyword">int</span>[][] prerequisites)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] indegree=<span class="keyword">new</span> <span class="keyword">int</span>[numCourses];</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; adjacency=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;numCourses;i++)&#123;</span><br><span class="line">        adjacency.add(<span class="keyword">new</span> ArrayList&lt;&gt;());</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span>[] p:prerequisites)&#123;</span><br><span class="line">        indegree[p[<span class="number">0</span>]]++; <span class="comment">//每个节点的入度值</span></span><br><span class="line">        <span class="comment">//邻接表,注意这里别搞反了,这里记录的是p[1]所有的出度节点</span></span><br><span class="line">        adjacency.get(p[<span class="number">1</span>]).add(p[<span class="number">0</span>]); </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//课程id</span></span><br><span class="line">    Queue&lt;Integer&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;numCourses;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(indegree[i]==<span class="number">0</span>)&#123;</span><br><span class="line">            queue.add(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">int</span> cid=queue.poll();</span><br><span class="line">        numCourses--;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> id:adjacency.get(cid)) &#123; <span class="comment">//cid --&gt; id</span></span><br><span class="line">            <span class="comment">//该节点的所有邻接节点入度--</span></span><br><span class="line">            indegree[id]--;</span><br><span class="line">            <span class="keyword">if</span>(indegree[id]==<span class="number">0</span>)&#123;</span><br><span class="line">                queue.add(id);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> numCourses==<span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="210-课程表-II"><a href="#210-课程表-II" class="headerlink" title="210. 课程表 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/course-schedule-ii/" >210. 课程表 II<i class="fas fa-external-link-alt"></i></a></h2><p>现在你总共有 <em>n</em> 门课需要选，记为 <code>0</code> 到 <code>n-1</code>。</p>
<p>在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: <code>[0,1]</code></p>
<p>给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。</p>
<p>可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">2</span>, [[<span class="number">1</span>,<span class="number">0</span>]] </span><br><span class="line">输出: [<span class="number">0</span>,<span class="number">1</span>]</span><br><span class="line">解释: 总共有 <span class="number">2</span> 门课程。要学习课程 <span class="number">1</span>，你需要先完成课程 <span class="number">0</span>。因此，正确的课程顺序为 [<span class="number">0</span>,<span class="number">1</span>] 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">4</span>, [[<span class="number">1</span>,<span class="number">0</span>],[<span class="number">2</span>,<span class="number">0</span>],[<span class="number">3</span>,<span class="number">1</span>],[<span class="number">3</span>,<span class="number">2</span>]]</span><br><span class="line">输出: [<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>] or [<span class="number">0</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">3</span>]</span><br><span class="line">解释: 总共有 <span class="number">4</span> 门课程。要学习课程 <span class="number">3</span>，你应该先完成课程 <span class="number">1</span> 和课程 <span class="number">2</span>。并且课程 <span class="number">1</span> 和课程 <span class="number">2</span> 都应该排在课程 <span class="number">0</span> 之后。</span><br><span class="line">     因此，一个正确的课程顺序是 [<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>] 。另一个正确的排序是 [<span class="number">0</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">3</span>] 。</span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ol>
<li>输入的先决条件是由<strong>边缘列表</strong>表示的图形，而不是邻接矩阵。详情请参见<a class="link"   target="_blank" rel="noopener" href="http://blog.csdn.net/woaidapaopao/article/details/51732947" >图的表示法<i class="fas fa-external-link-alt"></i></a>。</li>
<li>你可以假定输入的先决条件中没有重复的边。</li>
</ol>
<p><strong>提示:</strong></p>
<ol>
<li>这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。</li>
<li><a class="link"   target="_blank" rel="noopener" href="https://www.coursera.org/specializations/algorithms" >通过 DFS 进行拓扑排序<i class="fas fa-external-link-alt"></i></a> - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。</li>
<li>拓扑排序也可以通过 <a class="link"   target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224802?fr=aladdin&fromid=2148012&fromtitle=%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2" >BFS<i class="fas fa-external-link-alt"></i></a> 完成。</li>
</ol>
<p><strong>解法一</strong></p>
<p>BFS做法，和上面一样</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//BFS拓扑排序</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] findOrder(<span class="keyword">int</span> numCourses, <span class="keyword">int</span>[][] prerequisites) &#123;</span><br><span class="line">    <span class="keyword">int</span>[] indegree=<span class="keyword">new</span> <span class="keyword">int</span>[numCourses]; <span class="comment">//入度数</span></span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; adjacency=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;numCourses;i++)&#123;</span><br><span class="line">        adjacency.add(<span class="keyword">new</span> ArrayList&lt;&gt;());</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span>[] pre:prerequisites)&#123;</span><br><span class="line">        indegree[pre[<span class="number">0</span>]]++;</span><br><span class="line">        adjacency.get(pre[<span class="number">1</span>]).add(pre[<span class="number">0</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> k=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span>[] res=<span class="keyword">new</span> <span class="keyword">int</span>[numCourses];</span><br><span class="line">    Queue&lt;Integer&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;numCourses;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(indegree[i]==<span class="number">0</span>)&#123;</span><br><span class="line">            queue.add(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="keyword">int</span> cur=queue.poll();</span><br><span class="line">        res[k++]=cur;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> c:adjacency.get(cur))&#123;</span><br><span class="line">            indegree[c]--;</span><br><span class="line">            <span class="keyword">if</span>(indegree[c]==<span class="number">0</span>)&#123;</span><br><span class="line">                queue.add(c);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> k==numCourses?res:<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>DFS的做法，比BFS更有意思一点，其实就是个不断判环的过程，图相关的还是不太熟悉啊</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//DFS的解法</span></span><br><span class="line"><span class="keyword">int</span> k=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] findOrder(<span class="keyword">int</span> numCourses, <span class="keyword">int</span>[][] prerequisites) &#123;</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; adjacency=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;numCourses;i++)&#123;</span><br><span class="line">        adjacency.add(<span class="keyword">new</span> ArrayList&lt;&gt;());</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] mark=<span class="keyword">new</span> <span class="keyword">int</span>[numCourses];</span><br><span class="line">    <span class="keyword">int</span>[] res=<span class="keyword">new</span> <span class="keyword">int</span>[numCourses];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span>[] pre:prerequisites)&#123;</span><br><span class="line">        adjacency.get(pre[<span class="number">0</span>]).add(pre[<span class="number">1</span>]); <span class="comment">//注意这个区别</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;numCourses;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(dfs(adjacency,i,mark,res)) <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">0</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">dfs</span><span class="params">(List&lt;List&lt;Integer&gt;&gt; adj,<span class="keyword">int</span> cur,<span class="keyword">int</span>[] mark,<span class="keyword">int</span>[] res)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(mark[cur]==<span class="number">1</span>) <span class="keyword">return</span> <span class="keyword">true</span>;  <span class="comment">//正在访问</span></span><br><span class="line">    <span class="keyword">if</span>(mark[cur]==<span class="number">2</span>) <span class="keyword">return</span> <span class="keyword">false</span>; <span class="comment">//节点已经访问完（之前已经学了）</span></span><br><span class="line">    mark[cur]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> c:adj.get(cur))&#123;</span><br><span class="line">        <span class="keyword">if</span>(dfs(adj,c,mark,res))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    mark[cur]=<span class="number">2</span>;</span><br><span class="line">    <span class="comment">//cur的先决课程是没环的，所以可以学cur</span></span><br><span class="line">    res[k++]=cur; </span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="365-水壶问题"><a href="#365-水壶问题" class="headerlink" title="365. 水壶问题"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/water-and-jug-problem/" >365. 水壶问题<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>有两个容量分别为 _x_升 和 _y_升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 _z_升 的水？</p>
<p>如果可以，最后请用以上水壶中的一或两个来盛放取得的 _z升 _水。</p>
<p>你允许：</p>
<ul>
<li>  装满任意一个水壶</li>
<li>  清空任意一个水壶</li>
<li>  从一个水壶向另外一个水壶倒水，直到装满或者倒空</li>
</ul>
<p><strong>示例 1:</strong> (From the famous )</p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: x = <span class="number">3</span>, y = <span class="number">5</span>, z = <span class="number">4</span></span><br><span class="line">输出: True</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: x = <span class="number">2</span>, y = <span class="number">6</span>, z = <span class="number">5</span></span><br><span class="line">输出: False</span><br></pre></td></tr></table></figure>


<p><strong>解法一</strong></p>
<p>暴力BFS的解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canMeasureWater</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> z)</span> </span>&#123;</span><br><span class="line">    Queue&lt;<span class="keyword">int</span>[]&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> capX = x;</span><br><span class="line">    <span class="keyword">int</span> capY = y;</span><br><span class="line">    queue.add(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;x, y&#125;);</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty()) &#123;</span><br><span class="line">        <span class="keyword">int</span>[] cur = queue.poll();</span><br><span class="line">        <span class="keyword">int</span> cx = cur[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">int</span> cy = cur[<span class="number">1</span>];</span><br><span class="line">        <span class="keyword">if</span> (cx==z || cy==z || cx+cy==z) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//清空x</span></span><br><span class="line">        addQueue(<span class="number">0</span>, cy, queue);</span><br><span class="line">        <span class="comment">//清空y</span></span><br><span class="line">        addQueue(cx, <span class="number">0</span>, queue);</span><br><span class="line">        <span class="comment">//装满x</span></span><br><span class="line">        addQueue(capX, cy, queue);</span><br><span class="line">        <span class="comment">//装满y</span></span><br><span class="line">        addQueue(cx, capY, queue);</span><br><span class="line">        <span class="comment">//x--&gt;y</span></span><br><span class="line">        addQueue(Math.max(<span class="number">0</span>, cx-capY+cy), Math.min(capY, cy+cx), queue);</span><br><span class="line">        <span class="comment">//y--&gt;x</span></span><br><span class="line">        addQueue(Math.min(capX, cy+cx), Math.max(<span class="number">0</span>, cy-capY+cx), queue);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addQueue</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, Queue&lt;<span class="keyword">int</span>[]&gt; queue)</span></span>&#123;</span><br><span class="line">    <span class="keyword">long</span> hashCode = x * (<span class="keyword">long</span>)<span class="number">1e9</span>+<span class="number">7</span> + y;</span><br><span class="line">    <span class="keyword">if</span> (!visit.contains(hashCode)) &#123;</span><br><span class="line">        queue.add(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;x, y&#125;);</span><br><span class="line">        visit.add(hashCode);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong><br>数学解法，涉及到一些数学定理（贝祖定理），我也不是很懂（就是搞懂过两天也忘了）</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canMeasureWater</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> z)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(x+y&lt;z) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">if</span>(x==<span class="number">0</span> || y==<span class="number">0</span>) <span class="keyword">return</span> z==<span class="number">0</span> || x+y==z;</span><br><span class="line">    <span class="keyword">return</span> z%gcd(x,y)==<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">gcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(b==<span class="number">0</span>) <span class="keyword">return</span> a;</span><br><span class="line">    <span class="keyword">return</span> gcd(b,a%b);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="单调栈"><a href="#单调栈" class="headerlink" title="单调栈"></a><em>单调栈</em></h2><blockquote>
<p>单独开辟出新的专题 <a href="http://imlgw.top/2020/08/28/leetcode-dan-diao-zhan/">LeetCode单调栈</a></p>
</blockquote>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：LeetCode栈&amp;队列</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2019-10-01 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2019/10/01/627d9e22/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/10/10/26679fc/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">LeetCode回溯&amp;递归</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2019/09/24/c279d77a/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">AQS源码解析（上）</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2019/10/01/627d9e22/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#20-%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7"><span class="nav-number">1.</span> <span class="nav-text">20. 有效的括号</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#678-%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">2.</span> <span class="nav-text">678. 有效的括号字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#921-%E4%BD%BF%E6%8B%AC%E5%8F%B7%E6%9C%89%E6%95%88%E7%9A%84%E6%9C%80%E5%B0%91%E6%B7%BB%E5%8A%A0"><span class="nav-number">3.</span> <span class="nav-text">921. 使括号有效的最少添加</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#394-%E5%AD%97%E7%AC%A6%E4%B8%B2%E8%A7%A3%E7%A0%81"><span class="nav-number">4.</span> <span class="nav-text">394. 字符串解码</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#344-%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">5.</span> <span class="nav-text">344. 反转字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#150-%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC"><span class="nav-number">6.</span> <span class="nav-text">150. 逆波兰表达式求值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#71-%E7%AE%80%E5%8C%96%E8%B7%AF%E5%BE%84"><span class="nav-number">7.</span> <span class="nav-text">71. 简化路径</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#225-%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88"><span class="nav-number">8.</span> <span class="nav-text">225. 用队列实现栈</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#232-%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97"><span class="nav-number">9.</span> <span class="nav-text">232. 用栈实现队列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#155-%E6%9C%80%E5%B0%8F%E6%A0%88"><span class="nav-number">10.</span> <span class="nav-text">155. 最小栈</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#779-%E7%AC%ACK%E4%B8%AA%E8%AF%AD%E6%B3%95%E7%AC%A6%E5%8F%B7"><span class="nav-number">11.</span> <span class="nav-text">779. 第K个语法符号</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#50-Pow-x-n"><span class="nav-number">12.</span> <span class="nav-text">50. Pow(x, n)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5222-%E5%88%86%E5%89%B2%E5%B9%B3%E8%A1%A1%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">13.</span> <span class="nav-text">5222. 分割平衡字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1249-%E7%A7%BB%E9%99%A4%E6%97%A0%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7"><span class="nav-number">14.</span> <span class="nav-text">1249. 移除无效的括号</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#856-%E6%8B%AC%E5%8F%B7%E7%9A%84%E5%88%86%E6%95%B0"><span class="nav-number">15.</span> <span class="nav-text">856. 括号的分数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#946-%E9%AA%8C%E8%AF%81%E6%A0%88%E5%BA%8F%E5%88%97"><span class="nav-number">16.</span> <span class="nav-text">946. 验证栈序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#NC560-%E6%89%93%E5%AD%97"><span class="nav-number">17.</span> <span class="nav-text">NC560.打字</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#BFS%E5%B9%BF%E6%90%9C"><span class="nav-number">18.</span> <span class="nav-text">BFS广搜</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#279-%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0"><span class="nav-number">19.</span> <span class="nav-text">279. 完全平方数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#127-%E5%8D%95%E8%AF%8D%E6%8E%A5%E9%BE%99"><span class="nav-number">20.</span> <span class="nav-text">127. 单词接龙</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#542-01-%E7%9F%A9%E9%98%B5"><span class="nav-number">21.</span> <span class="nav-text">542. 01 矩阵</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1306-%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F-III"><span class="nav-number">22.</span> <span class="nav-text">1306. 跳跃游戏 III</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5314-%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F-IV"><span class="nav-number">23.</span> <span class="nav-text">5314. 跳跃游戏 IV</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#690-%E5%91%98%E5%B7%A5%E7%9A%84%E9%87%8D%E8%A6%81%E6%80%A7"><span class="nav-number">24.</span> <span class="nav-text">690. 员工的重要性</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1311-%E8%8E%B7%E5%8F%96%E4%BD%A0%E5%A5%BD%E5%8F%8B%E5%B7%B2%E8%A7%82%E7%9C%8B%E7%9A%84%E8%A7%86%E9%A2%91"><span class="nav-number">25.</span> <span class="nav-text">1311. 获取你好友已观看的视频</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#399-%E9%99%A4%E6%B3%95%E6%B1%82%E5%80%BC"><span class="nav-number">26.</span> <span class="nav-text">399. 除法求值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#301-%E5%88%A0%E9%99%A4%E6%97%A0%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7"><span class="nav-number">27.</span> <span class="nav-text">301. 删除无效的括号</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#994-%E8%85%90%E7%83%82%E7%9A%84%E6%A9%98%E5%AD%90"><span class="nav-number">28.</span> <span class="nav-text">994. 腐烂的橘子</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1162-%E5%9C%B0%E5%9B%BE%E5%88%86%E6%9E%90"><span class="nav-number">29.</span> <span class="nav-text">1162. 地图分析</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#207-%E8%AF%BE%E7%A8%8B%E8%A1%A8"><span class="nav-number">30.</span> <span class="nav-text">207. 课程表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#210-%E8%AF%BE%E7%A8%8B%E8%A1%A8-II"><span class="nav-number">31.</span> <span class="nav-text">210. 课程表 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#365-%E6%B0%B4%E5%A3%B6%E9%97%AE%E9%A2%98"><span class="nav-number">32.</span> <span class="nav-text">365. 水壶问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8D%95%E8%B0%83%E6%A0%88"><span class="nav-number">33.</span> <span class="nav-text">单调栈</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
